Finding Prime Numbers Using Python
เขียนโปรแกรมหาจำนวนเฉพาะอย่างง่ายๆในห้าไอเดียโดยใช้ Python
ไอเดียแรก
จำนวนเฉพาะคือจำนวนเต็มบวกใดๆที่ไม่มีจำนวนเต็มบวกอื่นๆหารมันลงตัว
1 2 3 4 5 6 7 8 9 10 11 12 13 | # prime1.py 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 จะเร็วกว่าเล็กน้อย ส่วนรายละเอียดนั้นเราจะไม่กล่าวถึงในที่นี้
ไอเดียที่สอง
เนื่องจากบางจำนวนที่ถูกนำมาหารนั้นเป็นตัวประกอบของอีกจำนวน ดังนั้นเราจึงสามารถลดจำนวนตัวหารเหลือแค่จำนวนที่ไม่มีจำนวนอื่นเป็นตัวประกอบ ซึ่งก็คือจำนวนเฉพาะที่มีค่าน้อยจำนวนที่ต้องการจะหานั่นเอง
1 2 3 4 5 6 7 8 9 10 11 12 13 | # prime2.py 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | # prime3.py 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 |
ไอเดียที่สี่
เราสามารถใช้หน่วยความจำของคอมพิวเตอร์มาช่วยในการคำนวณได้โดยใช้วิธีซีฟของเอราทอสเทนีส ซึ่งความเร็วที่ได้มาเพิ่มนั้นจะถูกแลกกับหน่วยความจำที่เสียไประหว่างคำนวณ
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | # prime4.py 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 |
ทดลองความเร็วของทั้งสี่ตัวอย่างบนเครื่องผม โดยให้หาจำนวนเฉพาะที่มีค่าต่ำกว่าหนึ่งแสน เราจะได้ผลลัพท์ตามคาด
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | poomk@gemini:/tmp/prime$ time ./prime1.py >/dev/null 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) คือใช้ซีฟหาจำนวนเฉพาะขนาดต่ำๆก่อน แล้วนำจำนวนเฉพาะนั้นไปหาจำนวนเฉพาะที่สูงขึ้นไปโดยใช้วิธีเดิม
1 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 | # prime5.py: Hybrid Sieve-Iterative 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 จะได้
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | poomk@gemini:/tmp/prime$ time ./prime3.py >/dev/null 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 |
จากผลลัพท์นี้สรุปได้คร่าวๆว่า ซีฟช่วยคุณได้จริงๆ
ดังนั้นถ้าคุณต้องการหาจำนวนเฉพาะที่มีขนาดเกินพันล้านแล้วละก็ เดินไปซื้อแรมมาใส่แล้วค่อยรันยังเร็วกว่า