Find All Prime Numbers Up To n

Given a non-negative integer n, output all prime numbers that are less than or equal to n using the Sieve of Eratosthenes algorithm.

The Sieve of Eratosthenes is an efficient algorithm to find all primes less than a given number. It works by iteratively marking the multiples of each prime starting from 2. In mathematical notation, the algorithm uses the property that for every prime p, the multiples p^2, p^2+p, p^2+2p, ... are composite. In LaTeX, this can be written as:

$$ \text{For each prime } p, \quad \{ p^2, p^2+p, p^2+2p, \dots \} \subset \{1,2,\dots,n\} \setminus \{p\}. $$

Your task is to implement this algorithm. If there are no primes (for example, when n is less than 2), the output should be empty.

inputFormat

The input consists of a single integer n (\( n \geq -10^9 \)).

Input is read from standard input.

outputFormat

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

Output is written to standard output.

10

2 3 5 7