Thuật toán khám nghiệm Số nguyên tố của một số nguyên dương, cùng rất thuật toán tìm UCLN của nhì số tự nhiên và thoải mái là những bài bác toán đặc biệt quan trọng trong Lập trình.
Bạn đang xem: Tìm số nguyên tố
Kiểm tra tính nguyên tố là bài toán kiểm tra xem một số tự nhiên n có phải là số nguyên tố giỏi không. Bài toán này đặc biệt quan trọng trở nên đặc trưng khi các hệ mật mã khoá công khai ra đời.
1. Số yếu tố là gì?
Số thành phần (prime) là số từ bỏ nhiên to hơn 1, chỉ có hai ước số là một trong những và chủ yếu nó. Theo có mang này thì các số 2, 3, 5, 7, 11,… là những số nguyên tố, trong các số đó số 2 là số yếu tắc chẵn duy nhất.
Ví dụ: 7 là số nhân tố vì trong tầm từ 2 mang lại 6 không tồn trên số nào cơ mà 7 phân chia hết cả.
2. Những Thuật toán bình chọn Số nhân tố Đơn Giản
Phương pháp đơn giản dễ dàng nhất để kiểm tra một trong những n gồm là số nguyên tố không là kiểm tra xem nó gồm chia hết cho các số m nằm trong vòng 2 mang đến n-1 hay không.
Nếu n phân tách hết đến một trong các số m nào đó thì n không là số nguyên tố (còn được hotline là hợp số composite). Ngược lại, trường hợp n không phân tách hết cho bất kỳ số m nào thì kết lianaj n là số nguyên tố.
Thực ra việc kiểm tra cùng với m từ bỏ 2 mang lại n-1 là không nên thiết, mà chỉ việc kiểm tra đến $sqrtn$ là đủ. Bởi vì nếu n là đúng theo số thì nó chắc hẳn rằng có ước số không vượt thừa sqrt(n).
Lặp từng thành phần với bước nhảy 1 mang lại n-1
Giả sử bắt buộc kiểm tra số n có phải là số nguyên tố hay không thì quá trình thực hiện tại như sau:
Bước 1: Nhập vào nBước 2: kiểm soát nếu n thì kết luận n không bắt buộc là số nguyên tốBước 3: Lặp từ 2 tới (n-1), nếu trong tầm này mãi sau số mà n chia hết thì kết luận n không buộc phải là số nguyên tố, ngược lại n là số nguyên tố.Độ phức hợp của thuật toán trên là $O(n)$.
Lặp từng phần tử với cách nhảy 2
Theo định nghĩa thì số 2 là số yếu tắc chẵn duy nhất, bởi vậy ta sẽ loại 2 ra khỏi vòng lặp cùng trong thân vòng lặp chỉ kiểm tra những số lẻ mà thôi, biện pháp này sẽ tối ưu hơn cách 1 khôn cùng nhiều.
Bước 1: Nhập vào n;Bước 2: khám nghiệm nếu n thì kết luận n không hẳn là số nguyên tố;Bước 3: đánh giá nếu n = 2 thì tóm lại n là số nguyên tố;Bước 4: Kiểm tra giả dụ n > 2 với chẵn thì kết luận n chưa phải là số nguyên tố;Bước 5. Lặp tự 3 cho tới (n-1), bước nhảy là 2 nếu trong vòng này mãi mãi số mà n chia không còn thì kết luận n không đề nghị 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 vày lặp tới n-1, bọn họ chỉ phải lặp những số tự 2 cho sqrt(n), nếu n chia không còn cho một trong những số kia thì n không cần là số nguyên tố. Trái lại thì n là số nguyên tố.
Độ phức tạp của thuật toán bên trên là $O(sqrtn)$.
3. Về tối ưu thuật toán bình chọn số nguyên tố
Chúng ta có thể tối ưu thuật toán trên bằng cách chỉ ra n không phân chia hết cho các số nguyên tố nhỏ tuổi hơn nó. Tuy nhiên, họ lại chưa chắc chắn được những số nguyên tố nhỏ hơn nó là những số nào (Bạn hoàn toàn có thể sử dụng phương pháp sàng số yếu tố – Sàng Eratosthenes nhằm tìm ra các số nguyên tố nhỏ dại hơn số n mang đến trước). đề nghị ta sử dụng tác dụng sau đây:
Tất cả đa số số nguyên tố to hơn 3 đều sở hữu dạng 6k ± 1 (vì 6k, 6k ± 2, là rất nhiều số chẵn; 6k + 3 thì chia hết cho 3).
Do đó, chúng ta chỉ đề nghị kiểm tra các số bao gồm dạng 6k ± 1 từ 2 đến √n, nếu n chia không còn cho trong số những số đó thì n không nên là số nguyên tố. Trái lại thì n là số nguyên tố.
def is_prime(n: int) -> bool: """Primality kiểm tra using 6k+-1 optimization.""" if n 1 if n % 2 == 0 or n % 3 == 0: return False i = 5 while i ** 2
4. Những Thuật toán soát sổ Số yếu tắc Nâng Cao
Các biện pháp kiểm tra số nguyên tố kể trên bao gồm độ đúng mực tuyệt đối nhưng cân nặng tính toán vô cùng lớn. Theo Wiki thì bọn họ còn có những phương pháp khác để khám nghiệm tính nhân tố của một số với một độ đúng mực cho trước.Kiểm tra theo xác suất
Các phép kiểm tra tính yếu tố hay dùng nhất là những thuật toán ngẫu nhiên.
Giả sử có một mệnh đề Q(p,a) nào kia đúng với tất cả số nguyên tố phường và một số trong những tự nhiên a . Giả dụ n là một số tự nhiên lẻ cùng mệnh đề Q(n,a) đúng với một a được rước ngẫu nhiên, lúc ấy a có khả năng là một vài nguyên tố.
Ta chỉ dẫn một thuật toán, kết luận rằng n là số nguyên tố. Nó là 1 thuật toán thiên nhiên hay thuật toán xác suất. Trong những thuật toán một số loại này, dùng một kiểm tra hốt 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ể tóm lại một hòa hợp số là số nguyên tố. Bởi đó, phương pháp này không đúng chuẩn một bí quyết tuyệt đối.
Xác suất sai của phép kiểm tra rất có thể giảm xuống nhờ vào việc chọn một dãy độc lập các số a; so với mỗi số a tỷ lệ để thuật toán kết luận một vừa lòng số là số nhân tố là nhỏ tuổi hơn một phần 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ơ phiên bản của một phép kiểm tra thốt nhiên là:Chọn một trong những ngẫu nhiên a.Kiểm tra một hệ thức nào kia giữa số a cùng số n vẫn cho. Nếu hệ thức sai thì chắc hẳn rằng n là một hợp số (số a là “bằng chứng” chứng minh n là phù hợp số) và dừng thuật toán.Nếu hệ thức đúng, bọn họ lặp lại hai cách trên cho tới khi đạt được một vài lần định trước hoặc gặp gỡ trường hòa hợp dừng thuật toán.Sau các lần thử, ví như hệ thức đúng với tương đối nhiều giá trị của a, ta nói theo một cách khác rằng n “có năng lực cao” là số nguyên tố chứ không hề thể chắc chắn rằng n là số nguyên tố. Tất yếu là chúng ta sẽ tìm biện pháp tăng “khả năng” này lên bằng phương pháp thực hiện tại nhiều đo lường hơn.
Các hệ thức thường xuyên sử dụngNếu phường là một số 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 soát sổ tính nguyên tố bỗng nhiên là:
Phép đánh giá tính nhân tố của Fermat (kiểm tra Fermat). Đây là phép thử heuristic; mặc dù ít fan sử dung phép thử này.Kiểm tra Miller-Rabin và kiểm soát Solovay-Strassen. Cùng với mỗi thích hợp số n, tối thiểu 3/4 (với kiểm tra Miller-Rabin) hoặc 50% (Với đánh giá Solovay-Strassen) những số a là bởi chứng chứng tỏ n là hợp số).Xem thêm: Permalink - Permanlinks
Các phép soát sổ tất định
Vào năm 2002, Manindra Agrawal, Nitin Saxena và Neeraj Kayal lời khuyên một lời giải tất định soát sổ tính nguyên tố, là khám nghiệm AKS, có công dụng chạy trong O((log n)12). Trên thực tế thuật toán này chạy lờ đờ hơn các phương pháp xác suất.
Các phương pháp này, mời các bạn đọc tham khảo thêm tại https://en.wikipedia.org/wiki/Primality_test