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.