Wikipedia

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

Duyệt lịch sử tương tác
← Thay đổi trướcThay đổi sau →
Nội dung được xóa Nội dung được thêm vào
Trực quanMã wiki
Không có tóm lược sửa đổi
Dòng 23:
Giả ngữ sau đây mô tả thuật toán này:
 
<pre>
// giới hạn tìm kiếm
limit ← 1000000
 
// Khởikhởi tạo sànglưới lọc
is_prime(i) ← false, ∀ i ∈ [5, limit]
 
// đưa vào số nguyên tố ứng cử:
// put in candidate primes:
// những số nguyên có một số lẻ
// integers which have an odd number of
// các dạng bậc 2.
// representations by certain quadratic forms
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
// eliminate composites by sieving
for n in [5, √limit]:
if is_prime(n):
// n islà primesố nguyên tố, omitbỏ multiplesqua ofcác itsbội squaresố bậc 2 của nó; thisđiều này islà
// sufficient because composites which managed to get
// on the list cannot be square-free
Hàng 54 ⟶ 55:
for n in [5, limit]:
if is_prime(n): print n
</pre>
 
{{sơ khai}}
Lấy từ “https://vi.wikipedia.org/wiki/Sàng_Atkin”