Sum of Primes

Given a positive integer n, your task is to compute the sum of all prime numbers that are less than or equal to n.

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. In other words, if p is prime then it is only divisible by 1 and p.

You can use the Sieve of Eratosthenes algorithm to efficiently generate all primes ≤ n. Recall that the Sieve of Eratosthenes works by marking as composite the multiples of each prime, starting from 2.

For example, if n = 10, the prime numbers are \(2, 3, 5, 7\) and their sum is \(2 + 3 + 5 + 7 = 17\).

inputFormat

The input consists of a single integer n (where 1 ≤ n ≤ 10⁶) provided via standard input.

outputFormat

Output a single integer representing the sum of all prime numbers less than or equal to n. The result should be printed to standard output.

10

17