Find Prime Numbers Less Than N

Given an integer \( n \), output all prime numbers that are strictly less than \( n \). A number \( p \) is prime if it is greater than 1 and has no positive divisors other than 1 and itself. Use the Sieve of Eratosthenes algorithm to generate the list of primes efficiently.

The Sieve of Eratosthenes works by marking the multiples of each prime starting from 2. The remaining unmarked numbers which are greater than 1 are prime numbers. The algorithm can be described using the equation:

[ \text{for } p = 2 \text{ to } \sqrt{n},\quad \text{if } p \text{ is prime then mark all multiples } kp \text{ (with } k \geq p) \text{ as composite.} ]

Your task is to implement this algorithm in a program that reads an integer from stdin and prints the prime numbers less than that integer to stdout separated by a single space. If there are no primes, output an empty line.

inputFormat

The input consists of a single integer \( n \) (\( 0 \leq n \leq 10^5 \)).

Input is provided via stdin.

outputFormat

Output the list of all prime numbers strictly less than \( n \) in ascending order, separated by a single space. If there are no primes, output an empty line.

The output should be written to stdout.

10

2 3 5 7