Khác biệt giữa bản sửa đổi của “Sàng Atkin”

{{thiếu nguồn gốc}}{{wikify}}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.

Contents

* 1 Thuật giải

* 2 Giả ngữ

* 6 Liên kết ngoài

 

 

Trong thuật toán:

* Đả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ố ở <math>4*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.

* Còn lại, 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.

Giả ngữ sau đây mô tả thuật toán này: