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.
مصفاة إراتوستينس
وجد عالم الرياضيات اليوناني إراتوستينس الأعداد الأولية دون القسمة على أي شيء: اكتب الأعداد، ثم اشطب مضاعفات كل عدد أولي.
[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. · اضغط تشغيل لرؤية المخرجات هنا.