Sieve of Eratosthenes

Lab Python Intermediate 20 points

Read n and print how many primes are ≤ n and the largest of them, using a sieve.

Input

One integer 2–1,000,000.

Output

count largest

Example

Input

Output

10 29

Sample input available Sample output available

Editor

Python

Hints

Cross out multiples of each prime, starting from its square.

Solution explanation

The sieve finds all primes up to n in about O(n log log n) time.

Show solution

n = int(input())
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
i = 2
while i * i <= n:
    if is_prime[i]:
        for j in range(i * i, n + 1, i):
            is_prime[j] = False
    i += 1
primes = [i for i, p in enumerate(is_prime) if p]
print(len(primes), primes[-1])

Output

Answer