Số nguyên tố là một số nguyên dương chỉ chia hết cho 1 hoặc chính nó. Tìm một số có phải là số nguyên tố hay không là một thách thức lập trình thú vị trong một thời gian dài. Hơn nữa, có các loại menthods khác nhau và chúng có hiệu quả khác nhau. Trong bài viết này, chúng ta sẽ xem xét ba phương pháp như vậy và đánh giá phương pháp nào hiệu quả hơn về thời gian thực hiện chúng.
Kiểm tra tất cả các số chia
Đây là một chương trình chuyển tiếp trong đó chúng tôi lấy mọi số nguyên từ 1 đến một nhỏ hơn số đã cho và tiếp tục kiểm tra xem số đó có chia cho bất kỳ số nào trong số này không. Nếu không tìm thấy số nào có thể chia hết số này thì số đó là số nguyên tố.
Ví dụ
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
Đầu ra
Chạy đoạn mã trên cho chúng ta kết quả sau -
Count of prime numbers till 10000 is 1229 Time Elapsed is: 2.3100001812
Các hệ số cho đến Căn bậc hai (N)
Về mặt toán học, người ta thấy rằng chỉ cần tìm các thừa số cho đến căn bậc hai của số mà chúng ta đang kiểm tra là đủ. Cách tiếp cận này làm giảm số lần lặp lại và do đó sẽ nhanh hơn mà chúng ta có thể kiểm tra như bên dưới. Dưới đây là logic để thực hiện ý tưởng này.
-
Chúng tôi tìm ra căn bậc hai của số đang được kiểm tra giá trị nguyên tố.
-
Chúng tôi chia số với từng giá trị cho đến giá trị căn bậc hai bắt đầu từ giá trị 2, để kiểm tra xem có phần dư nào còn lại không.
-
Nếu tại bất kỳ bước nào ở trên, phần còn lại bên trái bằng 0, thì số đó không phải là số nguyên tố.
Ví dụ
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
Đầu ra
Chạy đoạn mã trên cho chúng ta kết quả sau -
Count of prime numbers till 10000 is 1229 Time Elapsed is: 0.0529999732971
Rây Eratosthenes
Trong phương pháp này, chúng tôi loại bỏ các số không phải là số nguyên tố hoặc hợp số để có được các số nguyên tố cho đến số cụ thể. Vì vậy, dưới đây là các bước chúng tôi làm theo để đạt được điều đó.
-
Lập danh sách các số nguyên liên tiếp từ 2 đến số đó cho đến khi chúng ta muốn tìm tất cả các số nguyên tố.
-
Lấy số đầu tiên, tức là 2 và tạo danh sách tất cả các bội số của nó. Loại bỏ danh sách bội số này khỏi danh sách ban đầu nhưng không phải là 2. Lặp lại điều này cho số tiếp theo, tức là 3, v.v. cho các số tiếp theo. Xin lưu ý rằng chúng tôi chỉ loại bỏ các bội số chứ không phải số chính nó. Vì vậy, 5 hoặc 11 không bao giờ bị loại nhưng 10 và 22 bị loại.
-
Sau tất cả các loại bỏ, danh sách còn lại là danh sách các số nguyên tố cho đến số được hỏi.
Ví dụ
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
Đầu ra
Chạy đoạn mã trên cho chúng ta kết quả sau -
2 3 5 7 11 13 17 19 23 Time Elapsed is: 0.0