prime = [2] for i inxrange(3, 100000):
flag = True# สมมุติว่าจำนวน i เป็นจำนวนเฉพาะ for j inxrange(2, i): # จำนวน j ใดๆที่มีค่าน้อยกว่า i ต้องหารจำนวนนี้ไม่ลงตัว (ยกเว้น 1) if(i % j == 0): # แต่ถ้าหารได้ลงตัว (มีเศษเป็น 0)
flag = False# เราก็พบว่าจำนวนนั้นไม่ใช่จำนวนเฉพาะ break# ออกจากลูปทันที if flag == True: # ถ้าพิสูจน์แล้วว่าเป็นจำนวนเฉพาะจริงๆ
prime.append(i)# ให้ใส่ค่านั้นเข้าไปในตัวแปร prime
print prime
สังเกตว่าผมใช้คำสั่ง xrange แทน range เพราะเมื่อต้องการวนรอบเป็นจำนวนรอบมากๆแล้ว xrange จะเร็วกว่าเล็กน้อย ส่วนรายละเอียดนั้นเราจะไม่กล่าวถึงในที่นี้
prime = [2] for i inxrange(3, 100000):
flag = True for j in prime: # จำนวน j ใดๆที่เป็นจำนวนเฉพาะและมีค่าน้อยกว่า i ต้องหารจำนวนนี้ไม่ลงตัว if(i % j == 0):
flag = False break if flag == True:
prime.append(i)
print prime
ไอเดียที่สาม
ลดจำนวนตัวที่ต้องวนหารลง เนื่องจากจำนวนเต็มใดๆ j สูงสุดที่จะหาจำนวนเต็มใดๆ i ได้นั้น จะต้องมีค่าไม่มากไปกว่ารากที่สองของ i
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
# prime3.py
prime = [2] for i inxrange(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)
for i inxrange(2, n): if primeArr[i] == 0: # ถ้าจำนวนนั้นเป็นจำนวนเฉพาะ for j inxrange(i *2, n, i): # จำนวนอื่นๆที่จำนวนนั้นเป็นตัวประกอบจะไม่ใช่จำนวนเฉพาะ
primeArr[j] = 1
prime = [] for i inxrange(2, n): if primeArr[i] == 0: # เก็บจำนวนเฉพาะไว่ในตัวแปร prime
prime.append(i)
for i inxrange(2, n): if primeArr[i] == 0: for j inxrange(i *2, n, i):
primeArr[j] = 1
prime = [] for i inxrange(2, n): if primeArr[i] == 0:
prime.append(i)
for i inxrange(n, 20000000): # หาต่อจนถึงตัวที่ 20,000,000
flag = True for j in prime: if(j **2> i): break if(i % j == 0):
flag = False break if flag == True:
prime.append(i)
Finding Prime Numbers Using Python
เขียนโปรแกรมหาจำนวนเฉพาะอย่างง่ายๆในห้าไอเดียโดยใช้ Python
ไอเดียแรก
จำนวนเฉพาะคือจำนวนเต็มบวกใดๆที่ไม่มีจำนวนเต็มบวกอื่นๆหารมันลงตัว
2
3
4
5
6
7
8
9
10
11
12
13
prime = [2]
for i in xrange(3, 100000):
flag = True # สมมุติว่าจำนวน i เป็นจำนวนเฉพาะ
for j in xrange(2, i): # จำนวน j ใดๆที่มีค่าน้อยกว่า i ต้องหารจำนวนนี้ไม่ลงตัว (ยกเว้น 1)
if (i % j == 0): # แต่ถ้าหารได้ลงตัว (มีเศษเป็น 0)
flag = False # เราก็พบว่าจำนวนนั้นไม่ใช่จำนวนเฉพาะ
break # ออกจากลูปทันที
if flag == True: # ถ้าพิสูจน์แล้วว่าเป็นจำนวนเฉพาะจริงๆ
prime.append(i) # ให้ใส่ค่านั้นเข้าไปในตัวแปร prime
print prime
สังเกตว่าผมใช้คำสั่ง xrange แทน range เพราะเมื่อต้องการวนรอบเป็นจำนวนรอบมากๆแล้ว xrange จะเร็วกว่าเล็กน้อย ส่วนรายละเอียดนั้นเราจะไม่กล่าวถึงในที่นี้
ไอเดียที่สอง
เนื่องจากบางจำนวนที่ถูกนำมาหารนั้นเป็นตัวประกอบของอีกจำนวน ดังนั้นเราจึงสามารถลดจำนวนตัวหารเหลือแค่จำนวนที่ไม่มีจำนวนอื่นเป็นตัวประกอบ ซึ่งก็คือจำนวนเฉพาะที่มีค่าน้อยจำนวนที่ต้องการจะหานั่นเอง
2
3
4
5
6
7
8
9
10
11
12
13
prime = [2]
for i in xrange(3, 100000):
flag = True
for j in prime: # จำนวน j ใดๆที่เป็นจำนวนเฉพาะและมีค่าน้อยกว่า i ต้องหารจำนวนนี้ไม่ลงตัว
if (i % j == 0):
flag = False
break
if flag == True:
prime.append(i)
print prime
ไอเดียที่สาม
ลดจำนวนตัวที่ต้องวนหารลง เนื่องจากจำนวนเต็มใดๆ j สูงสุดที่จะหาจำนวนเต็มใดๆ i ได้นั้น จะต้องมีค่าไม่มากไปกว่ารากที่สองของ i
2
3
4
5
6
7
8
9
10
11
12
13
14
15
prime = [2]
for i in xrange(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)
print prime
ไอเดียที่สี่
เราสามารถใช้หน่วยความจำของคอมพิวเตอร์มาช่วยในการคำนวณได้โดยใช้วิธีซีฟของเอราทอสเทนีส ซึ่งความเร็วที่ได้มาเพิ่มนั้นจะถูกแลกกับหน่วยความจำที่เสียไประหว่างคำนวณ
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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)
print prime
ทดลองความเร็วของทั้งสี่ตัวอย่างบนเครื่องผม โดยให้หาจำนวนเฉพาะที่มีค่าต่ำกว่าหนึ่งแสน เราจะได้ผลลัพท์ตามคาด
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
real 6m16.043s
user 5m58.734s
sys 0m12.869s
poomk@gemini:/tmp/prime$ time ./prime2.py >/dev/null
real 0m20.074s
user 0m19.761s
sys 0m0.028s
poomk@gemini:/tmp/prime$ time ./prime3.py >/dev/null
real 0m0.703s
user 0m0.692s
sys 0m0.004s
poomk@gemini:/tmp/prime$ time ./prime4.py >/dev/null
real 0m0.570s
user 0m0.552s
sys 0m0.004s
ไอเดียที่ห้า
สืบเนื่องจากผลลัทพธืด้านบน เราเห็นว่าวิธีซีฟนั้นได้ผลลัพท์ดีที่สุด แต่เนื่องจากหน่วยความจำเรามีจำกัดทำให้เราไม่สามารถใช้ซีฟหาจำนวนเฉพาะมากๆได้ เราสามารถเอาสองวิธีนี้มาเขียนรวมกันแบบลูกครึ่ง (hybrid) คือใช้ซีฟหาจำนวนเฉพาะขนาดต่ำๆก่อน แล้วนำจำนวนเฉพาะนั้นไปหาจำนวนเฉพาะที่สูงขึ้นไปโดยใช้วิธีเดิม
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import numpy
n = 10000000 # ใช้ซีฟหาจำนวนเฉพาะที่มีค่าน้อยกว่า 10,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 xrange(n, 20000000): # หาต่อจนถึงตัวที่ 20,000,000
flag = True
for j in prime:
if (j ** 2 > i):
break
if (i % j == 0):
flag = False
break
if flag == True:
prime.append(i)
print prime
เปรียบเทียบ
ลองเปรียบเทียบความเร็วของตัวอย่างที่ 3, 5 (วิธีซีฟลูกครึ่ง), และ 4 (วิธีซีฟ) โดยหาจำนวนเฉพาะที่มีค่าน้อยกว่า 20,000,000 จะได้
2
3
4
5
6
7
8
9
10
11
12
13
14
15
real 9m19.625s
user 9m15.983s
sys 0m0.980s
poomk@gemini:/tmp/prime$ time ./prime5.py >/dev/null
real 6m14.933s
user 6m13.023s
sys 0m0.648s
poomk@gemini:/tmp/prime$ time ./prime4.py >/dev/null
real 1m24.342s
user 1m23.113s
sys 0m0.304s
จากผลลัพท์นี้สรุปได้คร่าวๆว่า ซีฟช่วยคุณได้จริงๆ
ดังนั้นถ้าคุณต้องการหาจำนวนเฉพาะที่มีขนาดเกินพันล้านแล้วละก็ เดินไปซื้อแรมมาใส่แล้วค่อยรันยังเร็วกว่า