You can generate the prime numbers by starting with an array [0 .. n] and then eliminating numbers that are not prime.
For example, let n = 100:
|
|
Prime numbers are atomic factors. They terminate a factoring process.
Therefore, 1 is not prime.
|
|
2 is prime. Therefore, any multiple of 2 is not prime.
The first multiple of 2 beyond 2 itself is 2^2 = 4.
We'll start there and set each multiple of 2 to 0:
|
|
The next prime is 3.
We will start at 3^2 and set each multiple of 3 to 0:
|
|
The next prime is 5.
Similarly, we will start at 5^2 and set each multiple of 5 to 0:
|
|
The next prime is 7.
You know the story.
|
|
The next prime is 11.
Its next multiple is 121, and that is beyond our original value of n.
Therefore, the numbers remaining in our list are either 0 or prime.
Let's get rid of the 0s:
|
|
|
|
We can summarize what we did for n = 100 and create a function that will work for any value of n:
|
|
|
|
|
|
|
|
Our sieve function seems to work. However, for values of n = 100,000 or above, the function takes awhile.
Sage itself contains an efficient way to generate a list of primes:
|
|