Sieve of Eratosthenes · Sàng Eratosthenes
Sieve of Eratosthenes
The Greek mathematician Eratosthenes found primes without dividing anything: write down the numbers, then cross out the multiples of each prime.
[True] * (n + 1) makes a list of n + 1 True values, one for each number from 0 to n. Mark 0 and 1 as not prime. Then, for each p still marked True, set every multiple of p from p * p onwards to False. The numbers still marked True at the end are the primes.
Lưới Eratosthenes
Nhà toán học Hy Lạp Eratosthenes đã tìm ra các số nguyên tố mà không chia bất cứ số nào: viết ra các số, sau đó gạch bỏ các bội số của mỗi số nguyên tố.
Hàm [True] * (n + 1) tạo ra một danh sách chứa n + 1 giá trị True, một giá trị cho mỗi số từ 0 đến n. Đánh dấu 0 và 1 là không phải số nguyên tố. Sau đó, với mỗi p vẫn còn được đánh dấu là True, đặt mọi bội số của p từ p * p trở lên thành False. Những số vẫn còn được đánh dấu là True ở cuối cùng chính là các số nguyên tố.
Write primes_up_to(n) that returns every prime number from 2 to n in order, using the sieve of Eratosthenes. primes_up_to(10) is [2, 3, 5, 7]. · Viết primes_up_to(n) trả về tất cả các số nguyên tố từ 2 đến n theo thứ tự, sử dụng sàng Eratosthenes. primes_up_to(10) là [2, 3, 5, 7].
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.