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) = 6number = a * b và 1 <= a <= 6
number = 48
= 1 * 48
= 2 * 24
= 3 * 16
= 4 * 12
= 6 * 8
sqrt(48) = 6.928203230275509number = 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 TrueChạ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
numbercần check là số chẵn thì chắc chắnnumberkhông phải số nguyên tố - Nếu
numberlà 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 TrueChạy thử với bộ test
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)
.gif)
Hình minh họa cho thấy thuật toán đơn giản để tìm số nguyên tố và các bội số
Các số tô màu giống nhau là cùng một họ mà dẫn đầu (đậm hơn) sẽ là số nguyên tố
Á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 TrueNế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 TrueTiế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ố
53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997 1009 1013 1019 1021 1031 1033 1039 1049 1051 1061 1063 1069 1087 1091 1093 1097 1103 1109 1117 1123 1129 1151 1153 1163 1171 1181 1187 1193 1201 1213 1217 1223 1229 1231 1237 1249 1259 1277 1279 1283 1289 1291 1297 1301 1303 1307 1319 1321 1327 1361 1367 1373 1381 1399 1409 1423 1427 1429 1433 1439 1447 1451 1453 1459 1471 1481 1483 1487 1489 1493 1499 1511 1523 1531 1543 1549 1553 1559 1567 1571 1579 1583 1597 1601 1607 1609 1613 1619 1621 1627 1637 1657 1663 1667 1669 1693 1697 1699 1709 1721 1723 1733 1741 1747 1753 1759 1777 1783 1787 1789 1801 1811 1823 1831 1847 1861 1867 1871 1873 1877 1879 1889 1901 1907 1913 1931 1933 1949 1951 1973 1979 1987 1993 1997 1999 2003 2011 2017 2027 2029 2039 2053 2063 2069 2081 2083 2087 2089 2099 2111 2113 2129 2131 2137 2141 2143 2153 2161 2179 2203 2207 2213 2221 2237 2239 2243 2251 2267 2269 2273 2281 2287 2293 2297 2309 2311 2333 2339 2341 2347 2351 2357 2371 2377 2381 2383 2389 2393 2399 2411 2417 2423 2437 2441 2447 2459 2467 2473 2477 2503 2521 2531 2539 2543 2549 2551 2557 2579 2591 2593 2609 2617 2621 2633 2647 2657 2659 2663 2671 2677 2683 2687 2689 2693 2699 2707 2711 2713 2719 2729 2731 2741 2749 2753 2767 2777 2789 2791 2797 2801 2803
Thực hiện kiểm tra dãy số trên là hợp số hay số nguyên tố.
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))Kết quả thu được khá ấn tượng
not a prime: []
Có nghĩa là tất cả các số ở dãy số trên đều là số nguyên tố. Bổ sung thêm điều thú vị trên vào function
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 TrueChạy thử với bộ dữ liệu test cho các function bên trên, chúng ta thu được kết quả:
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.0005003999997370556Vớ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. Tạm kết
Ngoài cách áp dụng phép sàng Eratosthenes để tối ưu bài toán tìm số nguyên tố, chúng ta còn có thể tham khảo thêm các giải thuật khác như Lucas Pseudoprimes, Baillie and Wagstaff, Miller-Rabin,...
