Sieve of Eratosthenes

It’s possible to find all the prime numbers smaller than n a lot faster than performing a primality check for each and every number from 2 to n. We can change the approach from checking each number to proactively removing all the numbers from the list which we know are not going to be prime.

As a start, we can have all the numbers from 2 to n marked as “possibly prime”. We then can remove all the multiples of 2 from that list and mark 2 as “definitely prime”. After that, we can remove all the multiples of 3 from the list and mark 3 as “definitely prime”. We then skip 4 as it was already removed from the list of possible prime numbers when we were processing 2. The next number to consider will be 5 and we’ll remove all the multiples for 5 as well. We will skip 6 as we marked it as not prime when we were processing 2. We can continue this process until we reach n.

Simulation of the Sieve of Eratosthenes. Click on the numbers and try to enable all the prime numbers, while making all the others disabled.

Interesting Properties and Optimizations of the Algorithm

A great consequence of removing all the multiples of a prime number p from the list of “possibly primes” starting from the smallest (2), and then gradually increasing the prime p, is that instead of processing all the multiples 2·p, 3·p, 4·p, 5·p... we can immediately start from p·p. As all the multiples of p like 2·p, 3·p, 4·p, 5·p have already been removed from the list of “possibly primes” when we were processing the numbers 2, 3, 5… the first number that hasn’t been touched yet is the p·p.

So, when we start processing p=3, we can directly start from 9 as 6 was already removed when we were processing the number 2. Similarly, when we start processing p=5, we can directly start from 25 as 10 (10 = 2·5) was removed from the list when we were processing the number 2, 15 (15 = 3·5) was removed from the list when we were processing the number 3, and finally, 20 (20 = 4·5) was removed when the number 2 was being processed.

prime = [True] * n                    # prime[i] = True => i is a prime number
prime[0] = prime[1] = False           # 0 and 1 are not prime

for i in range(2, n):                 # Loop from 2 to n
    if prime[i]:                      # if i is prime => mark all the multiples of i as not prime
        for j in range(i * i, n, i):  # we loop from `i * i` as all the multiples of i smaller have already been marked before
            prime[j] = False

Sieve of Eratosthenes to find all the prime numbers smaller than n.

Let’s simulate this process for n=100:

prime = [False, False, True, True, ..., True] of size 100

i = 2 ⇒ prime[2] = True ⇒ for j in 4, 6, 8, ... 100 and mark prime[j]=False

i = 3 ⇒ prime[3] = True ⇒ for j in 9, 12, ... 100 and mark prime[j]=False

i = 4 ⇒ prime[4] = False

i = 5 ⇒ prime[5] = True ⇒ for j in 25, 30, ... 100 and mark prime[j]=False

i = 6 ⇒ prime[6] = False

i = 7 ⇒ prime[7] = True ⇒ for j in 49, 56, ... 100 and mark prime[j]=False

i = 8 ⇒ prime[8] = False

i = 9 ⇒ prime[9] = False

i = 10 ⇒ prime[10] = False

i = 11 ⇒ prime[11] = True ⇒ for j in [empty] and mark prime[j]=False

We can stop here as i * i is already larger than n. Therefore, we won’t be marking any of the primes as False from this point on. So, we can loop through the list and print all the primes that are smaller than 100 here.

This approach is significantly faster and performs operations. This is a really big improvement! Doing operations instead of is a huge difference. Going back to the algorithm that had to work for 10 years (3650 days) to complete a calculation if it did n operations, and 2 months (61 days) in case it did operations, for operations it would only need less than 4 days!

One more optimization that’s mentioned in the simulation is to loop i from 2 up to as the inner loop starts from i·i, and therefore for all the numbers larger than the square root of n, we won’t be marking any numbers as prime[j] = False in the inner loop (the inner for loop’s upper bound is n).

Input

The first line of the input contains a single integer n (2 ≤ n ≤ ).

Output

The program should print all the prime numbers smaller than or equal to n.

Examples

Input	Output
8	2 3 5 7
17	2 3 5 7 11 13 17
19	2 3 5 7 11 13 17 19

Interesting Properties and Optimizations of the Algorithm

Input

Output

Examples

Constraints

To check your solution you need to sign in

Sign in to continue