Sieve of Eratosthenes

In this problem, you are required to implement the Sieve of Eratosthenes algorithm to compute all prime numbers up to a given number n. The algorithm works by iteratively marking the multiples of each prime number starting from 2. It can be formally described by the following formula:

\( \text{For } n \geq 2, \; \text{let } S = \{2,3,\dots,n\} \). For each number \( p \in S \), remove all multiples of \( p \) (i.e., numbers of the form \( p\times k \) for \( k \geq 2 \)) from \( S \). The remaining numbers are the primes up to \( n \).

If no primes exist (i.e. when \( n < 2 \)), output nothing.

inputFormat

The input consists of a single integer n (\(0 \leq n \leq 10^6\)) provided via standard input.

outputFormat

Output all the prime numbers less than or equal to n in increasing order, separated by a single space. If there are no primes, output an empty line.

1