Sàng Atkin

Trong toán học, sàng nguyên tố 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.

Thuật toán

• Tất cả các số dư là số dư khi chia cho 60 (chia cho 60 và xét số dư).
• Tất cả các số, bao gồm cả x và y đều là số nguyên dương.
• Đảo một ô trong sàng nghĩa là thay đổi đánh dấu (là số nguyên tố hoặc không) thành ngược lại.

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:
   • Nếu số đó chia 60 dư 1, 13, 17, 29, 37, 41, 49, hoặc 53, đảo đánh dấu cho các số ở ${\displaystyle 4*x^{2}+y^{2}}$ = số đang xét.
   • Nếu số đó chia 60 dư 7, 19, 31, hoặc 43, đảo các ô ${\displaystyle 3*x^{2}+y^{2}}$ = số đang xét.
   • Nếu số đó chia 60 dư 11, 23, 47, hoặc 59, đảo các số ${\displaystyle 3*x^{2}-y^{2}}$ = số đang xét.
   • Nếu không, không làm gì cả.
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.

Pseudocode

Pseudocode sau đây mô tả thuật toán này:

// giới hạn tìm kiếm
limit ← 1000000

// khởi tạo lưới lọc
is_prime(i) ← false, ∀ i ∈ [5, limit]

// đưa vào số nguyên tố ứng cử: 
// những số nguyên có một số lẻ 
// các dạng bậc 2.
for (x, y) in [1, √limit] × [1, √limit]:
 n ← 4x²+y²
 if (n ≤ limit) and (n mod 12 = 1 or n mod 12 = 5):
 is_prime(n) ← ¬is_prime(n)
 n ← 3x²+y²
 if (n ≤ limit) and (n mod 12 = 7):
 is_prime(n) ← ¬is_prime(n)
 n ← 3x²-y²
 if (x > y) and (n ≤ limit) and (n mod 12 = 11):
 is_prime(n) ← ¬is_prime(n)
 
// loại bỏ bằng cách sàng
for n in [5, √limit]:
 if is_prime(n):
 // n là số nguyên tố, bỏ qua các bội số bậc 2 của nó; điều này là
 // 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

Tham khảo