LongSpine.com Yes, we are lazy.

1Sep/090

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

จากผลลัพท์นี้สรุปได้คร่าวๆว่า ซีฟช่วยคุณได้จริงๆ

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

   

Recommended Reading

Recent Comments

Archives

Meta