Sieve of Eratosthenes
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ố.
Độ khó 5/5 · 400 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Write primes_up_to(n) that returns every prime number from 2 đến n in order, using the sieve of Eratosthenes. primes_up_to(10) là (is) [2, 3, 5, 7].
Nhấn Chạy để xem kết quả ở đây.