ง่ายสุดก็เช็คตั้งแต่ 2 จนถึง รากที่2ของจำนวนนั้น ไม่ก็เซ็คตั้งแต่ 1 ถึงตัวมัน เองว่า มีตัวหารลงตัวแค่2 ตัว หรือ ไม่ก็เช็คตั้งแค่ 2 ถึง ตัวมันเอง ว่าไม่มีอะไรหารลงตัว แต่แนะนำวิธีของเอราโทสเทเนส กล่าวไว้ว่า เมื่อหักเอาจำนวนที่ไม่ใช่จำนวนเฉพาะซึ่งอยู่หลังจำนวน เฉพาะออกไป จำนวนที่อยู่ถัดไปจะเป็นจำนวนเฉพาะ ฮ่า วิธีนี้ประสิทธิภาพดี

เช่นๆ เราเก็บ 1-100 ไว้ในอาเรย์ ตัวจำนวนเฉพาะ ตัวแรกที่เราเจอคือ 2 เพราะฉะนั้นเก็บไว้ ต่อไป เราก็เอาตัวที่ เป็น 2n ออก (อาจจะทำให้อารเรย์ช่องนั้นเป็น 0) แล้วเลื่อนอาร์เรย์ไป จนว่าจะเจอตัวที่ไม่ใช่ 0 ซึ่งเราพบว่า 3 คือตัวถัดไป เอามาเก็บไว้ แล้วก็ให้เอาตัว ที่เป็น 3n ออก แล้วก็ เลื่อนไปอีก จะเจอ 5 เพราะ 4 โดนเอาออกไปตั้งแต่ 2n แล้ว พอเราเจอ 5 เราก็เอาตัวที่หาร 5 ลงตัวออกเหมือนเดิม แล้วก็เลื่อนไป ก็เจอ 7 เพราะ 6 โดนเอาออกไปแล้ว ทำอย่างนี้ เป็นจำนวน nlog n ครั้ง อารเรย์ทั้งอาเรย์ก็ มีแต่จำนวนเฉพาะ ไปดูรูปที่นี่ http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

o=[] for i in range(1, 30): ... if (i%2 != 0 and i%3 != 0 and i%5 != 0 and i%7 != 0) or i in (2,3,5,7): ... o.append(i) ... print o [1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

หมายเหตุ: 1 ไม่ใช่จำนวนเฉพาะนะครับ หมายเหตุ 2: 2 mod 2 = 0 จึงไม่เข้าครับ เลย explicitly ใส่เข้าไปเลย หมายเหตุ 3: http://www.daniweb.com/code/snippet305.html

ขอบคุณมากๆๆคับผม

จา ที่ว่าพูดถึง หมายถึง จา พนม หรือเปล่าครับ?

ถ้าเขียนให้ครอบคลุมกว่านี้ผมแนะนำให้วนหามอดดูโล (modulo) จากจำนวนเฉพาะที่หามาก่อนหน้าน่าจะดีกว่านะ

prime = [2] for i in range(3, 100000): ... flag = True # สมมุติว่าจำนวน i เป็นจำนวนเฉพาะ ... for j in prime: # จำนวน j ใดๆที่เป็นจำนวนเฉพาะต้องหารจำนวนนี้ไม่ลงตัว ... if (i % j == 0): # แต่ถ้าดันหารได้ลงตัว (เหลือเศษ 0) ... flag = False # เราก็พบว่าจำนวนนั้นไม่ใช่จำนวนเฉพาะ ... break # ออกจากลูปทันที ... if flag == True: # ถ้าพิสูจน์แล้วว่าเป็นจำนวนเฉพาะจริงๆ ... prime.append(i) # ให้ใส่ค่านั้นเข้าไปในตัวแปร prime ... prime [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, ...]

ถ้าอยากให้เร็วขึ้นอีกทำตามที่คุณ nant บอก คือหารถึงแค่รากที่สองของมัน

prime = [2] for i in range(3, 100000): ... flag = True ... for j in prime: ... if (j ** 2 > i): # ถ้า j มีค่ามากกว่าตัวหารสุงสุดที่เป็นไปได้ (มีค่ามากกว่ารากที่สองของ i) ... break # ให้ออกจากลูป ... if (i % j == 0): ... flag = False ... break ... if flag == True: ... prime.append(i) ... prime [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, ...]

ส่วนวิธีซีฟของเอราทอสเทนีสนั้นเหมาะเวลาต้องการหาจำนวนเฉพาะที่ไม่ค่อยสูงมาก ข้อดีคือสามารถหาได้เร็วมาก ข้อเสียคือเปลืองหน่วยความจำ

import numpy

n = 100000 # หาจำนวนเฉพาะที่มีค่าน้อยกว่า 100000

primeArr = numpy.zeros(n) # สร้าง array ขนาด n primeArr[0] = 1 # 0 ไม่ใช่จำนวนเฉพาะ primeArr[1] = 1 # 1 ก็ไม่ใช่

for i in xrange(2, n): ... if primeArr[i] == 0: # ถ้าจำนวนนั้นเป็นจำนวนเฉพาะ ... for j in xrange(i * 2, n, i): # จำนวนอื่นๆที่จำนวนนั้นหารลงตัว ... primeArr[j] = 1 # ..จะไม่ใช่จำนวนเฉพาะ ... prime = []

for i in xrange(2, n): ... if primeArr[i] == 0: # เก็บจำนวนเฉพาะไว่ในตัวแปร prime ... prime.append(i) ... prime [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, …]

ลองมาดูความเร็วของสามตัวอย่างนี้บนเครื่องผมดู (หาจำนวนเฉพาะที่มีค่าต่ำกว่าหนึ่งแสน)

poomk@gemini:/tmp$ time ./prime1.py >/dev/null

real 0m19.622s user 0m19.581s sys 0m0.020s

poomk@gemini:/tmp$ time ./prime2.py >/dev/null

real 0m0.675s user 0m0.676s sys 0m0.000s

poomk@gemini:/tmp$ time ./prime3.py >/dev/null

real 0m0.535s user 0m0.504s sys 0m0.030s

เห็นได้ว่ามีแนวโน้มที่ดีขึ้นเรื่อยๆ

เนื่องจากหน่วยความจำเรามีจำกัด ทำให้เราไม่สามารถใช้ซีฟหาจำนวนเฉพาะมากๆได้ เราสามารถเอาสองวิธีนี้มาเขียนรวมกันแบบลูกครึ่ง (hybrid) คือใช้ซีฟหาจำนวนเฉพาะขนาดต่ำๆก่อน (เช่นต่ำกว่าหนึ่งล้าน) แล้วนำจำนวนเฉพาะนั้นไปหาจำนวนเฉพาะที่สูงขึ้นไปโดยใช้วิธีเดิม

import numpy

n = 1000000 # หาจำนวนเฉพาะที่มีค่าน้อยกว่า 1,000,000

primeArr = numpy.zeros(n) primeArr[0] = 1 primeArr[1] = 1

for i in xrange(2, n): ... if primeArr[i] == 0: ... for j in xrange(i * 2, n, i): ... primeArr[j] = 1 ... prime = []

for i in xrange(2, n): ... if primeArr[i] == 0: ... prime.append(i) ... for i in range(n, 2000000): # หาต่อจนถึงตัวที่ 2,000,000 ... flag = True ... for j in prime: ... if (j ** 2 > i): # ถ้า j มีค่ามากกว่าตัวหารสุงสุดที่เป็นไปได้ (มีค่ามากกว่ารากที่สองของ i) ... break # ให้ออกจากลูป ... if (i % j == 0): ... flag = False ... break ... if flag == True: ... prime.append(i) ... prime [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, ...]

ลองเปรียบเทียบความเร็วระหว่างใช้ซีฟช่วยกับการไม่ใช้ซีฟ ในการหาจำนวนเ)พาะที่ต่ำกว่าสองล้าน

poomk@gemini:/tmp$ time ./prime2.py >/dev/null

real 0m27.190s user 0m27.090s sys 0m0.096s

poomk@gemini:/tmp$ time ./prime4.py >/dev/null

real 0m20.422s user 0m20.369s sys 0m0.040s

อย่างไรก็ตามผมว่าไม่ควรเชื่อกับตัวเลขความเร็วมากนักเพราะนี่เป็นตัวอย่างแบบลวกๆ อยากให้มองที่แนวคิดมากกว่า

เขียนซะยาวเลย เผื่อมีคนอื่นเข้ามาดูแล้วอาจเป้นประโยชน์ (แบบว่าหลงมาเจอ)

LongSpine.com

---

LongSpine.com

ขอบคุณมากๆเลยครับสำหรับความช่วยเหลือ

ขอบคุณสำหรับทุกๆความช่วยเหลือครับ

ขอบคุณมากๆ

อันนี้เลยครับ สุดยอด (ผมก็กำลังทำการบ้านเรื่องนี้เหมือนกัน)

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes