ง่ายสุดก็เช็คตั้งแต่ 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

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

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