Sieve of Eratosthenes

Practice this coding question on Coding Gurukul.

Problem statement

Given n, print all prime numbers from 2 through n in increasing order using the Sieve of Eratosthenes. A prime number has exactly two positive divisors. Neither 0 nor 1 is prime. Start with candidate primes. For each prime p up to sqrt(n), mark its multiples from p*p onward as nonprime. If there are no primes up to n, print EMPTY. Use O(n) space and O(n log log n) time. Worked example The primes up to 12 are 2, 3, 5, 7 and 11.

Input format

One integer n.

Output format

Print space-separated primes up to n, or EMPTY.

Constraints

0 <= n <= 1000000.

Sample input

12

Sample output

2 3 5 7 11

Sign in to run or submit a solution in C++, Java or Python.