HÀM KIỂM TRA SỐ NGUYÊN TỐ

     
Thuật toán kiểm soát Số Nguyên Tố2. Các Thuật toán soát sổ Số nhân tố Đơn Giản4. Các Thuật toán kiểm tra Số thành phần Nâng Cao
Thuật toán kiểm soát Số Nguyên Tố

Thuật toán kiểm soát Số yếu tố của một số trong những nguyên dương, cùng rất thuật toán tra cứu UCLN của nhị số tự nhiên và thoải mái là những bài xích toán đặc biệt trong Lập trình.

Bạn đang xem: Hàm kiểm tra số nguyên tố

Kiểm tra tính nhân tố là bài toán kiểm tra xem một trong những tự nhiên n liệu có phải là số nguyên tố hay không. Việc này đặc trưng trở nên đặc trưng khi những hệ mật mã khoá công khai minh bạch ra đời.

1. Số nhân tố là gì?

Số thành phần (prime) là số tự nhiên lớn hơn 1, chỉ có hai ước số là một trong và chính nó. Theo khái niệm này thì các số 2, 3, 5, 7, 11,… là những số nguyên tố, trong đó số 2 là số yếu tắc chẵn duy nhất.


*

Ví dụ: 7 là số thành phần vì trong vòng từ 2 mang đến 6 không tồn tại số nào mà lại 7 chia hết cả.


2. Những Thuật toán đánh giá Số nhân tố Đơn Giản

Phương pháp dễ dàng nhất để kiểm tra một trong những n có là số nguyên tố không là khám nghiệm xem nó gồm chia hết cho các số m nằm trong khoảng 2 mang đến n-1 hay không.


Nếu n phân chia hết đến một trong những số m nào đó thì n ko là số thành phần (còn được call là hợp số composite). Ngược lại, giả dụ n không chia hết cho bất kì số m làm sao thì kết lianaj n là số nguyên tố.


Thực ra câu hỏi kiểm tra với m tự 2 cho n-1 là không yêu cầu thiết, mà chỉ cần kiểm tra mang lại $sqrtn$ là đủ. Vì nếu n là thích hợp số thì nó chắc chắn có mong số không vượt thừa sqrt(n).


Lặp từng thành phần với cách nhảy 1 mang đến n-1

Giả sử cần kiểm tra số n có nên là số nguyên tố hay không thì các bước thực hiện như sau:


Bước 1: Nhập vào nBước 2: soát sổ nếu n  thì kết luận n không nên là số nguyên tốBước 3: Lặp từ 2 tới (n-1), nếu trong vòng này trường tồn số mà n chia hết thì kết luận n không cần là số nguyên tố, ngược lại n là số nguyên tố.

Độ tinh vi của thuật toán trên là $O(n)$.


Lặp từng thành phần với cách nhảy 2

Theo quan niệm thì số 2 là số yếu tố chẵn duy nhất, vày vậy ta sẽ các loại 2 thoát ra khỏi vòng lặp với trong thân vòng lặp chỉ kiểm tra các số lẻ mà thôi, bí quyết này sẽ tối ưu hơn giải pháp 1 rất nhiều.


Bước 1: Nhập vào n;Bước 2: chất vấn nếu n  thì kết luận n chưa phải là số nguyên tố;Bước 3: soát sổ nếu n = 2 thì kết luận n là số nguyên tố;Bước 4: Kiểm tra trường hợp n > 2 cùng chẵn thì kết luận n không hẳn là số nguyên tố;Bước 5. Lặp từ bỏ 3 tới (n-1), cách nhảy là 2 nếu trong tầm này trường tồn số nhưng n chia không còn thì kết luận n không đề xuất là số nguyên tố, ngược lại n là số nguyên tố.

Lặp từng phần tử đến $sqrtn$

Để về tối ưu hơn, thay bởi lặp tới n-1, họ chỉ bắt buộc lặp những số tự 2 mang đến sqrt(n), nếu n chia hết cho trong số những số kia thì n không nên là số nguyên tố. Trái lại thì n là số nguyên tố.

Xem thêm: Tải Phần Mềm Cùng Học Toán Lớp 1 2 3 4 5 Miễn Phí Cho Các Bé Tiểu Học Nào!


Độ phức tạp của thuật toán trên là $O(sqrtn)$.

3. Về tối ưu thuật toán kiểm tra số nguyên tố

Chúng ta hoàn toàn có thể tối ưu thuật toán trên bằng phương pháp chỉ ra n không phân chia hết cho hầu như số nguyên tố bé dại hơn nó. Tuy nhiên, bọn họ lại chưa biết được các số nguyên tố nhỏ dại hơn nó là gần như số làm sao (Bạn hoàn toàn có thể sử dụng phương pháp sàng số yếu tắc – Sàng Eratosthenes nhằm tìm ra các số nguyên tố nhỏ dại hơn số n cho trước). Buộc phải ta sử dụng tác dụng sau đây:

Tất cả đều số nguyên tố lớn hơn 3 đều phải có dạng 6k ± 1 (vì 6k, 6k ± 2, là đông đảo số chẵn; 6k + 3 thì chia hết mang lại 3).

Do đó, chúng ta chỉ đề xuất kiểm tra những số có dạng 6k ± 1 từ 2 đến √n, nếu n chia hết cho trong những số kia thì n không yêu cầu là số nguyên tố. Trái lại thì n là số nguyên tố.


def is_prime(n: int) -> bool: """Primality test using 6k+-1 optimization.""" if n 1 if n % 2 == 0 or n % 3 == 0: return False i = 5 while i ** 2

4. Các Thuật toán khám nghiệm Số yếu tắc Nâng Cao

Các bí quyết kiểm tra số nguyên tố kể trên gồm độ chính xác tuyệt đối nhưng khối lượng tính toán cực kỳ lớn. Theo Wiki thì họ còn có những cách khác để bình chọn tính nhân tố của một trong những với một độ chính xác cho trước.


Kiểm tra theo xác suất

Các phép bình chọn tính thành phần hay cần sử dụng nhất là các thuật toán ngẫu nhiên.


Giả sử bao gồm một mệnh đề Q(p,a) nào kia đúng với mọi số nguyên tố p và một số trong những tự nhiên a . Nếu n là một số tự nhiên lẻ với mệnh đề Q(n,a) đúng với 1 a được lấy ngẫu nhiên, khi ấy a có tác dụng là một vài nguyên tố.

Ta chỉ dẫn một thuật toán, tóm lại rằng n là số nguyên tố. Nó là 1 trong những thuật toán thiên nhiên hay thuật toán xác suất. Trong số thuật toán các loại này, sử dụng một kiểm tra thiên nhiên sẽ không bao giờ tóm lại một số yếu tố là vừa lòng số nhưng lại có thể kết luận một vừa lòng số là số nguyên tố. Vày đó, phương thức này không đúng chuẩn một giải pháp tuyệt đối.


Xác suất không đúng của phép kiểm tra hoàn toàn có thể giảm xuống nhờ việc lựa chọn 1 dãy hòa bình các số a; nếu với mỗi số a phần trăm để thuật toán tóm lại một thích hợp số là số yếu tắc là nhỏ dại hơn một phần hai thì sau k lần test độc lập, phần trăm sai là nhỏ hơn 2^k, độ tin tưởng của thuật toán sẽ tăng lên theo k.


Cấu trúc cơ bạn dạng của một phép kiểm tra tự dưng là:Chọn một số ngẫu nhiên a.Kiểm tra một hệ thức nào đó giữa số a cùng số n đang cho. Ví như hệ thức không đúng thì chắc chắn là n là 1 hợp số (số a là “bằng chứng” minh chứng n là hợp số) cùng dừng thuật toán.Nếu hệ thức đúng, chúng ta lặp lại hai bước trên cho tới khi đạt được một số trong những lần định trước hoặc chạm chán trường hợp dừng thuật toán.

Sau nhiều lần thử, nếu như hệ thức đúng với khá nhiều giá trị của a, ta nói theo cách khác rằng n “có khả năng cao” là số nguyên tố chứ không cần thể chắc hẳn rằng n là số nguyên tố. Tất yếu là họ sẽ tìm giải pháp tăng “khả năng” này lên bằng cách thực hiện nay nhiều đo lường và tính toán hơn.


Các hệ thức thường sử dụng

Nếu p. Là một trong những nguyên tố thì


fp + 1 ≡ 0 (mod p) (với fp + 1 là số Fibonacci thứ p + 1 và p có dạng 5k ± 2)

Các phép đánh giá tính nguyên tố bất chợt là:


Phép bình chọn tính nguyên tố của Fermat (kiểm tra Fermat). Đây là phép thử heuristic; tuy nhiên ít người sử dung phép test này.Kiểm tra Miller-Rabin và soát sổ Solovay-Strassen. Với mỗi phù hợp số n, tối thiểu 3/4 (với bình chọn Miller-Rabin) hoặc 50% (Với kiểm tra Solovay-Strassen) những số a là bởi chứng minh chứng n là đúng theo số).

*


Các phép khám nghiệm tất định

Vào năm 2002, Manindra Agrawal, Nitin Saxena với Neeraj Kayal khuyến nghị một giải mã tất định bình chọn tính nguyên tố, là kiểm soát AKS, có khả năng chạy trong O((log n)12). Trên thực tế thuật toán này chạy chậm chạp hơn các phương thức xác suất.

Xem thêm: Mẹo Thực Hiện Cách Photo Tài Liệu Thu Nhỏ Nhanh Chóng Nhất, Cách Photo Nhỏ Bằng Máy In

Các phương pháp này, mời chúng ta đọc bài viết liên quan tại https://en.wikipedia.org/wiki/Primality_test


Categories Thuật toán, Python Tags dart, phù hợp số, prime, python, số nguyên tố, thuật toán Post navigation
Đề thi hsg lớp 12 môn hóa tỉnh Quảng Trị năm 2013
Sàng số yếu tắc (Sàng Eratosthenes)

Leave a bình luận Cancel reply

Comment

NameEmailWebsite

Save my name, email, & website in this browser for the next time I comment.


Search

Bài Viết Mới

WEBSITE BẠN BÈ


© 2022 O₂ Education| Dàn Karaoke| Micro ko Dây| Loa Karaoke JBL| Loa Âm Trần