การวิเคราะห์วิธีการต่างๆ เพื่อค้นหาจำนวนเฉพาะใน Python

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

ตรวจสอบตัวหารทั้งหมด

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

ตัวอย่าง

import time
#Function to check Prime Number
def check_prime(final_val):
   if final_val <= 1:
      return False
   for divisor in range(2,final_val):
      if final_val % divisor == 0:
         return False
      return True
# Track the Start Time
StartTime = time.time()
#Count the number of prime numbers
cnt = 0
for final_val in range(1,10001):
   x = check_prime(final_val)
   cnt += x
print 'Count of prime numbers till',final_val,'is ', cnt
# Track the End Time
EndTime = time.time()
print 'Time Elapsed is: ', EndTime - StartTime

ผลลัพธ์

การเรียกใช้โค้ดข้างต้นทำให้เราได้ผลลัพธ์ดังต่อไปนี้ -

Count of prime numbers till 10000 is 1229
Time Elapsed is: 2.3100001812

ปัจจัยจนถึงรากที่สอง(N)

ในทางคณิตศาสตร์ ยังพบว่า เพียงพอที่จะหาตัวประกอบจนถึงรากที่สองของจำนวนที่เรากำลังตรวจสอบอยู่ วิธีนี้ช่วยลดจำนวนการวนซ้ำ ดังนั้นควรเร็วกว่านี้ ซึ่งเราสามารถตรวจสอบได้ดังนี้ ตรรกะในการใช้แนวคิดนี้อยู่ด้านล่าง

• เราจะหารากที่สองของตัวเลขที่กำลังตรวจสอบหาค่าเฉพาะ

• เราหารตัวเลขด้วยค่าแต่ละค่าจนถึงค่ารากที่สองที่เริ่มต้นจากค่า 2 เพื่อตรวจสอบว่ายังมีเศษเหลืออยู่หรือไม่

• หากในขั้นตอนใดๆ ด้านบน เศษที่เหลือเป็นศูนย์ แสดงว่าจำนวนนั้นไม่ใช่จำนวนเฉพาะ

ตัวอย่าง

import math
import time
def is_prime(final_val):
   # 1 is not a prime number
   if final_val <= 1:
      return False
   i = 2
   while i <= math.floor(math.sqrt(final_val)):
   # Check if any remainders are cerated
      if final_val % i == 0:
         return False
      i += 1
   return True
# Track the Start Time
StartTime = time.time()
cnt = 0
for n in xrange(1, 10001):
   x = is_prime(n)
   cnt += x
print 'Count of prime numbers till',n,'is ', cnt
# Track the End Time
EndTime = time.time()
print 'Time Elapsed is: ', EndTime - StartTime

ผลลัพธ์

การเรียกใช้โค้ดข้างต้นทำให้เราได้ผลลัพธ์ดังต่อไปนี้ -

Count of prime numbers till 10000 is 1229
Time Elapsed is: 0.0529999732971

ตะแกรงของ Eratosthenes

ในวิธีนี้ เราจะกำจัดจำนวนเฉพาะหรือจำนวนเชิงประกอบเพื่อให้ได้จำนวนเฉพาะจนถึงจำนวนเฉพาะ ด้านล่างนี้คือขั้นตอนที่เราปฏิบัติตามเพื่อให้บรรลุเป้าหมายนั้น

• ทำรายการจำนวนเต็มที่เรียงต่อกันจาก 2 ไปเป็นจำนวนนั้นจนกว่าเราต้องการหาจำนวนเฉพาะทั้งหมด

• ใช้หมายเลขแรกเช่น 2 และสร้างรายการของทวีคูณทั้งหมด ลบรายการทวีคูณออกจากรายการเดิม แต่ไม่ใช่ 2 ทำซ้ำสำหรับหมายเลขถัดไปเช่น 3 และต่อไปสำหรับตัวเลขถัดไป โปรดทราบว่าเรากำลังตัดเฉพาะตัวคูณเท่านั้น ไม่ใช่ตัวตัวเลข ดังนั้น 5 หรือ 11 จะไม่ถูกกำจัด แต่ 10 และ 22 จะถูกกำจัด

• หลังจากการตัดออกทั้งหมด รายการที่เหลือคือรายการของจำนวนเฉพาะจนถึงจำนวนที่ถาม

ตัวอย่าง

import time
def sieve_method(n):
#Create a list of prime numbers
   prime_number_list = []
   for i in range(2, n+1):
# Capture the number if it si not in prime list
   if i not in prime_number_list:
      print (i)
# Add the number to the prime list number if it is a multiple
   for j in range(i*i, n+1, i):
      prime_number_list.append(j)
# Track the Start Time
StartTime = time.time()
cnt = 0
print(sieve_method(25))
# Track the End Time
EndTime = time.time()
print 'Time Elapsed is: ', EndTime - StartTime

ผลลัพธ์

การเรียกใช้โค้ดข้างต้นทำให้เราได้ผลลัพธ์ดังต่อไปนี้ -

2
3
5
7
11
13
17
19
23
Time Elapsed is: 0.0