Sieve of 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.
กรอง eratosthenes
นักคณิตศาสตร์กรีก eratosthenes หาเลขต้นแบบโดยไม่ทำการหาร: เขียนตัวเลขลง แล้วขีดฆ่าตัวคูณของแต่ละเลขต้นแบบ
[True] * (n + 1) สร้างลิสต์ของ n + 1 True ค่า โดยหนึ่งค่าสำหรับแต่ละจำนวนตั้งแต่ 0 ถึง n标记 0 และ 1 ว่าไม่ใช่จำนวนเฉพาะ จากนั้น สำหรับแต่ละ p ที่ยังถูก标记 True ตั้งค่าพหุคูณทั้งหมดของ p ตั้งแต่ p * p เป็นต้นไป เป็น False จำนวนที่ยังถูก标记 True ในตอนท้ายคือจำนวนเฉพาะ
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]. · เขียน primes_up_to(n) ที่ส่งกลับจำนวนเฉพาะทั้งหมดตั้งแต่ 2 ถึง n ตามลำดับ โดยใช้วิธีตะแกรงเอราโทสทีน primes_up_to(10) คือ [2, 3, 5, 7]
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่