Sàng nguyên tố Atkin Trong toán học, sàng Atkin là một thuật toán nhanh và hiện đại để tìm tất cả các số nguyên tố nhỏ hơn một số nguyên xác định. Đó là một thuật toán tối ưu từ sàng nguyên tố Eratosthenes: sàng Atkin chuẩn bị trước một số việc rồi sau đó đánh dấu các bội số của bình phương các số nguyên tố, chứ không phải là bội của các số nguyên tố. Thuật toán này được xây dựng bở A. O. L. Atkin và Daniel J. Bernstein. Contents [hide]
* 1 Thuật giải * 2 Giả ngữ * 3 Giải thích * 4 Độ phức tạp * 5 Tham khảo * 6 Liên kết ngoài
[edit] Thuật giải
Trong thuật toán:
1. Tạo bảng kết quả, điền vào 2, 3, và 5. 2. Tạo bảng sàng nguyên tố với các số nguyên dương; tất cả các số đánh dấu là không nguyên tố. 3. Với tất cả các số trong sàng:
4. Bắt đầu từ số nhỏ nhất trong sàng. 5. Lấy các số tiếp theo trong sàng được đánh dấu là prime. 6. Thêm vào danh sách kết quả. 7. Bình phương số đó và đánh dấu các bội số của số đó là không phải số nguyên tố. 8. Lặp lại bước 5 cho tới bước 8. [edit] Pseudocode Giả ngữ sau đây mô tả thuật toán này:
// giới hạn tìm kiếm limit ← 1000000
// Khởi tạo sàng is_prime(i) ← false, i ∈ [5, limit]
// put in candidate primes: // integers which have an odd number of // representations by certain quadratic forms for (x, y) in [1, √limit] × [1, √limit]:
n ← 4x²+y²
if (n ≤ limit) ∧ (n mod 12 = 1 ∨ n mod 12 = 5):
is_prime(n) ← ¬is_prime(n)
n ← 3x²+y²
if (n ≤ limit) ∧ (n mod 12 = 7):
is_prime(n) ← ¬is_prime(n)
n ← 3x²-y²
if (x > y) ∧ (n ≤ limit) ∧ (n mod 12 = 11):
is_prime(n) ← ¬is_prime(n)
// eliminate composites by sieving for n in [5, √limit]:
if is_prime(n):
// n is prime, omit multiples of its square; this is
// sufficient because composites which managed to get
// on the list cannot be square-free
is_prime(k) ← false, k ∈ {n², 2n², 3n², ..., limit}
print 2, 3 for n in [5, limit]:
if is_prime(n): print n
 |
Bài này đang được dịch từ ngôn ngữ khác. Nếu bạn có đủ khả năng xin góp sức dịch bài này. Nếu không tiếp tục được quan tâm, phần ngoại ngữ của bài sẽ bị xóa sau khoảng 1 tháng. Xin đừng quên chuyển các mục Chú thích, Tham khảo vào bài dịch để đáp ứng tiêu chuẩn. Xin tham khảo Hướng dẫn cách biên soạn bài để biết thêm chi tiết. |
This pseudocode is written for clarity. Repeated and wasteful calculations mean that it would run slower than the sieve of Eratosthenes. To improve its efficiency, faster methods must be used to find solutions to the three quadratics. At the least, separate loops could have tighter limits than [1, √limit].
[edit] Explanation
The algorithm completely ignores any numbers divisible by two, three, or five. All numbers with modulo-sixty remainder 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, or 58 are divisible by two and not prime. All numbers with modulo-sixty remainder 3, 9, 15, 21, 27, 33, 39, 45, 51, or 57 are divisible by three and not prime. All numbers with modulo-sixty remainder 5, 25, 35, or 55 are divisible by five and not prime. All these remainders are ignored.
All numbers with modulo-sixty remainder 1, 13, 17, 29, 37, 41, 49, or 53 have a modulo-four remainder of 1. These numbers are prime if and only if the number of solutions to 4x2 + y2 = n is odd and the number is squarefree (proven as theorem 6.1 of [1]).
All numbers with modulo-sixty remainder 7, 19, 31, or 43 have a modulo-six remainder of 1. These numbers are prime if and only if the number of solutions to 3x2 + y2 = n is odd and the number is squarefree (proven as theorem 6.2 of [1]).
All numbers with modulo-sixty remainder 11, 23, 47, or 59 have a modulo-twelve remainder of 11. These numbers are prime if and only if the number of solutions to 3x2 − y2 = n is odd and the number is squarefree (proven as theorem 6.3 of [1]).
None of the potential primes are divisible by 2, 3, or 5, so they can't be divisible by their squares. This is why squarefree checks don't include 22, 32, and 52.
[edit] Computational complexity
This sieve computes primes up to N using O(N/log log N) operations with only N1/2+o(1) bits of memory. The sieve of Eratosthenes uses O(N) operations and O(N1/2(log log N)/log N) bits of memory. These complexity estimates include simple optimizations, such as wheel factorization, and splitting the computation to smaller blocks.
 |
Bài này còn sơ khai. Mời bạn góp sức viết thêm để bài được hoàn thiện hơn. Xem phần trợ giúp về cách sửa bài. |
