Generating Prime Numbers The Sieve of Eratosthenes is an elegant algorithm for f
ID: 3532811 • Letter: G
Question
Generating Prime Numbers
The Sieve of Eratosthenes is an elegant algorithm for finding all of the prime numbers up to some limit n. The basic idea is to first create a list of numbers from 2 to n. The first number is removed from the list, and announced as a prime number, and all multiples of the number up to n are removed from the list. This process continues until the list is empty.
For example, if we wished to find all the primes up to 10, the list would originally contain [2, 3, 4, 5, 6, 7, 8, 9, 10]. The 2 is removed and announced to be prime. Then 4, 6, 8, and 10 are removed, since they are multiples of 2. That leaves [3, 5, 7, 9]. Repeating the process, 3 is announced as prime, and 9 is removed because it is a multiple of 9. That leaves [5, 7]. And so on.
Explanation / Answer
def sieve(n): m = (n-1) b = [True]*m i,p,ps = 0,3,[2] while p*pRelated Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.