Largest Prime Number Up To N

You are required to find the largest prime number that is less than or equal to a given integer n. The solution should implement the Sieve of Eratosthenes algorithm to generate the list of prime numbers up to n. If there is no prime number (i.e. when n < 2), the program should output None.

Recall that the Sieve of Eratosthenes works by iteratively marking the multiples of each prime, starting with the first prime number, 2. The steps can be expressed in LaTeX as follows:

\( \text{For } 2 \leq p \leq \sqrt{n}, \text{ mark all multiples } kp \text{ (with } k \geq p) \text{ as non-prime.} \)

Your program must read input from standard input (stdin) and write the answer to standard output (stdout).

inputFormat

The input consists of a single non-negative integer n (\(0 \leq n \leq 10^6\)). This value is provided via stdin.

outputFormat

Output the largest prime number less than or equal to n to stdout. If n is less than 2 and no prime number exists, output None.

10

7