Tìm Số Nguyên Tố Trong Lập Trình Bằng Cách Nào?
Chắc các bạn còn nhớ đến năm đầu tiên của cấp 2, một trong số các bài học "vỡ lòng" của môn số học là `Số nguyên tố` - các con số `cô đơn` khi lớn hơn 1 và chỉ chia hết cho 1 và chính nó.
Với các bạn không học sâu về toán thì số nguyên tố chỉ còn là một khái niệm, với những bạn học chuyên toán thì số nguyên tố sẽ đi kèm với một loạt các thử thách trong bộ môn đại số và giải tích. Với những bạn học công nghệ thông tin thì số nguyên tố là một thử thách khó khăn với hàng loạt các bài toán lập trình
Số nguyên tố là gì?
Nếu hỏi chị google "Định nghĩa số nguyên tố", câu trả lời chúng ta nhận được sẽ là: "-Theo wikipedia-, số nguyên tố là số tự nhiên lớn hơn 1 không phải là tích của hai số tự nhiên nhỏ hơn. Số tự nhiên lớn hơn 1 không phải là số nguyên tố được gọi là hợp số. Chẳng hạn, 5 là số nguyên tố bởi vì cách duy nhất để viết nó dưới dạng một tích, 1 × 5 hoặc 5 × 1, có một thừa số là chính số 5...."
Cách xác định một số nguyên tố với dân lập trình:
Theo như định nghĩa ở trên, cách đơn giản nhất để xác định number
có phải là số nguyên tố không là tạo ra một vòng lặp từ 2 đến number - 1
, nếu number
chia hết cho một số nào đó thì number
là một hợp số.
Code đơn giản được viết bằng python:
def is_prime_basic(number):
if number < 2:
return False
for value in range(2, number):
if number % value == 0:
return False
return True
Kiểm tra thử
import timeit
list_number = [164650, 39371, 339779, 909961, 120017 , 33901, 50377 , 563684, 61280, 375698]
total_time = 0
for number in list_number:
start = timeit.default_timer()
result = is_prime_basic(number)
stop = timeit.default_timer()
result = is_prime_basic(number)
print("{} is a prime number: {}.".format(number, result))
total_time += stop - start
print("Elapsed time: {}(second)".format(total_time))
Kết quả in ra màn hình
164650 is a prime number: False. 39371 is a prime number: True. 339779 is a prime number: False. 909961 is a prime number: False. 120017 is a prime number: True. 33901 is a prime number: False. 50377 is a prime number: True. 563684 is a prime number: False. 61280 is a prime number: False. 375698 is a prime number: False. Elapsed time: 0.029753100000107224(second)
Thực tế thì chúng ta không cần thực hiện vòng lặp từ 2
--> number - 1
vì nếu number = a * b với a <= b thì chắc chắn a <= sqrt(number)
Ví dụ:
number = 36
= 1 * 36
= 2 * 18
= 3 * 12
= 4 * 9
= 6 * 6
sqrt(36) = 6
number = a * b
và 1 <= a <= 6
number = 48
= 1 * 48
= 2 * 24
= 3 * 16
= 4 * 12
= 6 * 8
sqrt(48) = 6.928203230275509
number = a * b
và 1 <= a <= 6,9 ~ < 7
Như vậy chúng ta chỉ cần thực hiện vòng lặp từ 2 đến sqrt(number) + 1 là đã có thể kiểm tra được number
có phải là số nguyên tố hay không.
import math
def is_prime_sqrt(number):
if number < 2:
return False
max_range = int(math.sqrt(number)) + 1
for value in range(2, max_range):
if number % value == 0:
return False
return True
Chạy thử:
import timeit
list_number = [164650, 39371, 339779, 909961, 120017 , 33901, 50377 , 563684, 61280, 375698]
total_time = 0
for number in list_number:
start = timeit.default_timer()
result = is_prime_sqrt(number)
stop = timeit.default_timer()
print("{} is a prime number: {}.".format(number, result))
total_time += stop - start
print("Elapsed time: {}(second)".format(total_time))
164650 is a prime number: False.
39371 is a prime number: True.
339779 is a prime number: False.
909961 is a prime number: False.
120017 is a prime number: True.
33901 is a prime number: False.
50377 is a prime number: True.
563684 is a prime number: False.
61280 is a prime number: False.
375698 is a prime number: False.
Elapsed time: 0.00014700000019729487(second)
Với lần tối ưu vừa rồi đã giảm được kha khá thời gian thực hiện của function kiểm tra số nguyên tố. Nhưng chúng ta vẫn có thể áp dụng một số kiến thức toán học để thực hiện tối ưu tiếp bài toán này.
"Số 2 là số nguyên tố chẵn duy nhất" --> Dựa vào lưu ý này, chúng ta có thể triển khai tiếp 2 hành động
- Nếu
number
cần check là số chẵn thì chắc chắnnumber
không phải số nguyên tố - Nếu
number
là số lẻ thì thay vì đưa vòng lặp băt đầu từ 2 và bước nhảy 1 đơn vị thì chúng ta sẽ đưa vào vòng lặp bắt đầu từ 3 và bước nhảy 2 đơn vị.
import math
def is_prime_jump_2(number):
if number == 2:
return True
if number % 2 == 0 or number < 2:
return False
max_range = int(math.sqrt(number)) + 1
for value in range(3, max_range, 2):
if number % value == 0:
return False
return True
list_number = [164650, 39371, 339779, 909961, 120017 , 33901, 50377 , 563684, 61280, 375698]
total_time = 0
for number in list_number:
start = timeit.default_timer()
result = is_prime_jump_2(number)
stop = timeit.default_timer()
print("{} is a prime number: {}.".format(number, result))
total_time += stop - start
print("Elapsed time: {}(second)".format(total_time))
164650 is a prime number: False.
39371 is a prime number: True.
339779 is a prime number: False.
909961 is a prime number: False.
120017 is a prime number: True.
33901 is a prime number: False.
50377 is a prime number: True.
563684 is a prime number: False.
61280 is a prime number: False.
375698 is a prime number: False.
Elapsed time: 9.88000001598266e-05(second)
Con số của lần này cũng khá ấn tượng, giảm thêm so với lần trước kha khá nhiều
Tiếp tục tối ưu phương pháp tìm kiếm số nguyên tố, chúng ta có thể tham khảo đến phép sàng Eratosthenes (Sieve of Eratosthenes) . Cách thực hiện thuật toán này được mô tả tường minh bằng hình ảnh ví dụ sau: (nguồn ảnh wikipedia.org)
Áp dụng vào bài toán của chúng ta, ngoại trừ các số nguyên tố nhỏ nhất là 2, 3, 5; chúng ta sẽ dùng dấu hiệu chia hết cho 2, 3, 5 để loại bỏ bớt các hợp số.
def is_prime_optimal(number):
if number in [2, 3, 5]:
return True
if number % 2 == 0 or number % 3 == 0 or number % 5 == 0 or number < 2:
return False
max_range = int(math.sqrt(number)) + 1
for value in range(3, max_range, 2):
if number % value == 0:
return False
return True
Nếu liệt kê các số từ 1 đến 48, với 3 số nguyên tố đầu tiên là 2, 3, 5; bỏ qua các số chia hết cho 2, 3, 5 (đặt vào dấu ()
); chúng ta đã được các số như sau:
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) (33) (34) (35) (36) 37 (38) (39) (40) 41 (42) 43 (44) (45) (46) 47 (48)
Nhìn vào danh sách số phía trên, các số không có trong dấu ()
là: 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47. Và đây cũng là các số nguyên tố. Dựa vào lập luận này, chúng ta có thể cải tiến thêm thành function bên dưới.
def is_prime_optimal(number):
if number in [2, 3, 5]:
return True
if number % 2 == 0 or number % 3 == 0 or number % 5 == 0 or number < 2:
return False
if number < 49:
return True
max_range = int(math.sqrt(number)) + 1
for value in range(50, max_range, 2):
if number % value == 0:
return False
return True
Tiếp tục thực hiện "gấp thếp" các số nguyên tố mới tìm được ở bên trên 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47
theo phương pháp sàng Eratosthenes, chúng ta tiếp tục loại bỏ được các số hợp số.
def is_prime_optimal(number):
if number in [2, 3, 5]:
return True
if number % 2 == 0 or number % 3 == 0 or number % 5 == 0 or number < 2:
return False
if number < 49:
return True
if (number % 7) == 0 or (number % 11) == 0 or (number % 13) == 0 or (number % 17) == 0 or \
(number % 19) == 0 or (number % 23) == 0 or (number % 29) == 0 or (number % 31) == 0 or \
(number % 37) == 0 or (number % 41) == 0 or (number % 43) == 0 or (number % 47) == 0:
return False
max_range = int(math.sqrt(number)) + 1
for value in range(50, max_range, 2):
if number % value == 0:
return False
return True
Dễ dàng để nhận thấy số nguyên tố tiếp theo ngay sau 47
là số 53
; Thử thực hiện một phép lặp từ từ 49 đến nhỏ hơn 53^2 = 2809, lọc bỏ các hợp số thỏa mãn điều kiện chia hết cho 2, 3, 5 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47; chúng ta sẽ thu được dãy số.
list_number = []
# 53 * 53 = 2809
for number in range(49, 2809):
if number % 2 == 0 or number % 3 == 0 or number % 5 == 0 or \
(number % 7) == 0 or (number % 11) == 0 or (number % 13) == 0 or (number % 17) == 0 or \
(number % 19) == 0 or (number % 23) == 0 or (number % 29) == 0 or (number % 31) == 0 or \
(number % 37) == 0 or (number % 41) == 0 or (number % 43) == 0 or (number % 47) == 0:
continue
print(number, sep=" ", end=" ")
list_number.append(number)
Ta thu được 1 dãy số
lst_not_prime = []
for number in list_number:
if not is_prime_sqrt(number):
print("{} is not a prime".format(number))
lst_not_prime.append(number)
print("not a prime: {}".format(lst_not_prime))
is_prime_optimal
:def is_prime_optimal(number):
if number in [2, 3, 5]:
return True
if number % 2 == 0 or number % 3 == 0 or number % 5 == 0 or number < 2:
return False
if number < 49:
return True
if (number % 7) == 0 or (number % 11) == 0 or (number % 13) == 0 or (number % 17) == 0 or \
(number % 19) == 0 or (number % 23) == 0 or (number % 29) == 0 or (number % 31) == 0 or \
(number % 37) == 0 or (number % 41) == 0 or (number % 43) == 0 or (number % 47) == 0:
return False
if number < 2809:
return True
max_range = int(math.sqrt(number)) + 1
for value in range(53, max_range, 2):
if number % value == 0:
return False
return True
164650 is a prime number: False.
39371 is a prime number: True.
339779 is a prime number: False.
909961 is a prime number: False.
120017 is a prime number: True.
33901 is a prime number: False.
50377 is a prime number: True.
563684 is a prime number: False.
61280 is a prime number: False.
375698 is a prime number: False.
Elapsed time: 5.829999918205431e-05(second)
Tính đến đây, chúng ta đã có một function kiểm tra số nguyên tố khá là ưng ý, chúng ta sẽ thực hiện chạy một tập số để kiểm tra performance của các function phía trên.
Ví dụ: thực hiện sinh ngẫu nhiên một list chứa 10 số nguyên, thực hiện kiểm tra các số trong danh sách có phải là số nguyên tố không và đo đạc phép kiểm tra từng số cũng như tổng thời gian thực hiện kiểm tra 10 số trên.
Sau khi chạy script dưới đây, chúng ta thu được kết quả (kết quả này thay đổi khi chạy các scrip, tùy thuộc vào tốc độ xử lý của máy tính):
import math
import timeit
import random
def is_prime_basic(number):
if number < 2:
return False
for value in range(2, number):
if number % value == 0:
return False
return True
def is_prime_sqrt(number):
if number < 2:
return False
max_range = int(math.sqrt(number)) + 1
for value in range(2, max_range):
if number % value == 0:
return False
return True
def is_prime_optimal(number):
if number in [2, 3, 5]:
return True
if number % 2 == 0 or number % 3 == 0 or number % 5 == 0 or number < 2:
return False
if number < 49:
return True
if (number % 7) == 0 or (number % 11) == 0 or (number % 13) == 0 or (number % 17) == 0 or \
(number % 19) == 0 or (number % 23) == 0 or (number % 29) == 0 or (number % 31) == 0 or \
(number % 37) == 0 or (number % 41) == 0 or (number % 43) == 0 or (number % 47) == 0:
return False
if number < 2809:
return True
max_range = int(math.sqrt(number)) + 1
for value in range(53, max_range, 2):
if number % value == 0:
return False
return True
def random_all_array(length):
arr = []
for index in range(length):
arr.append(random.randint(1, 10**8))
return arr
def run_basic_function(number):
start = timeit.default_timer()
result = is_prime_basic(number)
stop = timeit.default_timer()
print("Basic-function {0}: {1}: {2}(second)".format(number, result, (stop - start)))
return stop - start
def run_sqrt_function(number):
start = timeit.default_timer()
result = is_prime_sqrt(number)
stop = timeit.default_timer()
print("Sqrt-function {0}: {1}: {2}(second)".format(number, result, (stop - start)))
return stop - start
def run_optimal_function(number):
start = timeit.default_timer()
result = is_prime_optimal(number)
stop = timeit.default_timer()
print("Optimal-function {0}: {1}: {2}(second)".format(number, result, (stop - start)))
return stop - start
def compare_performance():
list_number = random_all_array(10)
print(list_number)
basic_time = 0
sqrt_time = 0
optimal_time = 0
for number in list_number:
basic_time += run_basic_function(number)
sqrt_time += run_sqrt_function(number)
optimal_time += run_optimal_function(number)
print("Total elapsed time for `is_prime_basic` function ", basic_time)
print("Total elapsed time for `is_prime_sqrt` function ", sqrt_time)
print("Total elapsed time for `is_prime_optimal` function ", optimal_time)
# call to function
compare_performance()
[80909548, 64284912, 32561271, 59635875, 43704113, 42511163, 7564624, 62719360, 29119365, 49141585]
Basic-function 80909548: False: 3.000000106112566e-06(second)
Sqrt-function 80909548: False: 6.799999937356915e-06(second)
Optimal-function 80909548: False: 2.4000000848900527e-06(second)
Basic-function 64284912: False: 3.89999991057266e-06(second)
Sqrt-function 64284912: False: 5.599999894911889e-06(second)
Optimal-function 64284912: False: 1.3999999737279722e-06(second)
Basic-function 32561271: False: 2.699999868127634e-06(second)
Sqrt-function 32561271: False: 3.6999999792897142e-06(second)
Optimal-function 32561271: False: 1.2999998943996616e-06(second)
Basic-function 59635875: False: 2.4000000848900527e-06(second)
Sqrt-function 59635875: False: 3.2000000373955118e-06(second)
Optimal-function 59635875: False: 1.0999999631167157e-06(second)
Basic-function 43704113: True: 4.237569500000063(second)
Sqrt-function 43704113: True: 0.00046080000015535916(second)
Optimal-function 43704113: True: 0.0002480000000559812(second)
Basic-function 42511163: True: 4.04824050000002(second)
Sqrt-function 42511163: True: 0.0004547000000911794(second)
Optimal-function 42511163: True: 0.00024399999983870657(second)
Basic-function 7564624: False: 1.2000000424450263e-06(second)
Sqrt-function 7564624: False: 1.2999998943996616e-06(second)
Optimal-function 7564624: False: 6.000000212225132e-07(second)
Basic-function 62719360: False: 9.99999883788405e-07(second)
Sqrt-function 62719360: False: 1.300000121773337e-06(second)
Optimal-function 62719360: False: 4.999999418942025e-07(second)
Basic-function 29119365: False: 9.000000318337698e-07(second)
Sqrt-function 29119365: False: 1.199999815071351e-06(second)
Optimal-function 29119365: False: 4.999999418942025e-07(second)
Basic-function 49141585: False: 1.0999999631167157e-06(second)
Sqrt-function 49141585: False: 1.2999998943996616e-06(second)
Optimal-function 49141585: False: 6.000000212225132e-07(second)
Total elapsed time for `is_prime_basic` function 8.285826199999974
Total elapsed time for `is_prime_sqrt` function 0.0009398999998211366
Total elapsed time for `is_prime_optimal` function 0.0005003999997370556
Với kết quả như trên, chúng ta hoàn toàn có thể tin tưởng vào tốc độ xử lý của function
is_prime_optimal
.