imported>T.A.Halley: Thêm liên kết

2022-01-27T08:13:07Z

Thêm liên kết

Trang mới

{{Dead end|date=tháng 7 năm 2018}}

{{thiếu nguồn gốc}}

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 [[Phép chia|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.

:#Tạo bảng kết quả, điền vào 2, 3, và 5.
:#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ố.
:#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ố ở <math>4*x^2 + y^2</math> = số đang xét.
:#* Nếu số đó chia 60 dư 7, 19, 31, hoặc 43, đảo các ô <math>3*x^2 + y^2</math> = số đang xét.
:#* Nếu số đó chia 60 dư 11, 23, 47, hoặc 59, đảo các số <math>3*x^2- y^2</math> = số đang xét.
:#* Nếu không, không làm gì cả.
:#Bắt đầu từ số nhỏ nhất trong sàng.
:#Lấy các số tiếp theo trong sàng được đánh dấu là prime.
:#Thêm vào danh sách kết quả.
:#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ố.
:#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:

<pre>
// 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
</pre>

==Tham khảo==
{{tham khảo}}
{{sơ khai}}

[[Thể loại:Số học sơ cấp]]

Sàng Atkin - Lịch sử thay đổi

imported>T.A.Halley: Thêm liên kết