ในบทช่วยสอนนี้ เราจะดูวิธีการหาจำนวนเฉพาะ (Prime Number) แบบต่างๆ และเปรียบเทียบเวลาที่ใช้ในการทำงานของแต่ละวิธี โดยใช้โมดูล time ในการวัดเวลารัน
วิธีที่ 1: วิธีทั่วไป (Brute Force)
เป็นวิธีพื้นฐานในการหาจำนวนเฉพาะ
- ถ้าเลขน้อยกว่าหรือเท่ากับ 1 ให้คืนค่า False
- ถ้าเลขหารด้วยตัวเลขใดตัวหนึ่งลงตัว ให้คืนค่า False
- หลังจบลูป ให้คืนค่า True
ตัวอย่างโค้ด
import time
def is_prime(n):
if n <= 1:
return False
else:
for i in range(2, n):
if n % i == 0:
return False
return True
start_time = time.time()
primes = 0
for i in range(100000):
if is_prime(i):
primes += 1
print(f'Total primes in the range {primes}')
end_time = time.time()
print(f'Execution time: {end_time - start_time}')ผลลัพธ์
Total primes in the range 9594 Execution time: 63.1301212310791
วิธีที่ 2: ลดจำนวนรอบลูปด้วยรากที่สอง
ในวิธีนี้ เราลดจำนวนรอบการวนลูปโดยตรวจสอบเฉพาะจนถึงรากที่สองของ n
ตัวอย่างโค้ด
import time
import math
def is_prime(n):
if n <= 1:
return False
else:
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
return False
return True
start_time = time.time()
primes = 0
for i in range(100000):
if is_prime(i):
primes += 1
print(f'Total primes in the range {primes}')
end_time = time.time()
print(f'Execution time: {end_time - start_time}')ผลลัพธ์
Total primes in the range 9592 Execution time: 0.2039644718170166
วิธีที่ 3: ข้ามเลขคู่ (ยกเว้น 2)
เราทราบว่าเลขคู่ไม่ใช่จำนวนเฉพาะ (ยกเว้น 2) ดังนั้นเราสามารถข้ามเลขคู่ได้เพื่อลดเวลาลงอีก
ตัวอย่างโค้ด
import time
import math
def is_prime(n):
if n <= 1:
return False
elif n == 2:
return True
elif n > 2 and n % 2 == 0:
return False
else:
for i in range(3, int(math.sqrt(n)) + 1, 2):
if n % i == 0:
return False
return True
start_time = time.time()
primes = 0
for i in range(100000):
if is_prime(i):
primes += 1
print(f'Total primes in the range {primes}')
end_time = time.time()
print(f'Execution time: {end_time - start_time}')ผลลัพธ์
Total primes in the range 9592 Execution time: 0.10342741012573242
สรุป
จากการทดสอบพบว่า:
- วิธีที่ 1 ใช้เวลา ~63 วินาที (ช้ามาก)
- วิธีที่ 2 ใช้เวลา ~0.2 วินาที (เร็วกว่า ~300 เท่า)
- วิธีที่ 3 ใช้เวลา ~0.1 วินาที (เร็วกว่าวิธีที่ 2 อีก 2 เท่า)
การเพิ่มประสิทธิภาพอัลกอริทึมส่งผลต่อประสิทธิภาพอย่างมาก หากมีข้อสงสัย สามารถถามได้ในส่วนความคิดเห็น
