Primes up to N

Lab Python Intermediate 20 points

Read n and print all primes ≤ n on one line separated by spaces.

Input

One integer ≥ 2.

Output

One line.

Example

Input

Output

2 3 5 7 11 13 17 19 23 29

Sample input available Sample output available

Editor

Python

Hints

A number is prime if no smaller prime up to its square root divides it.

Reuse the primes you've already found.

Solution explanation

Only primes need testing as divisors, and only up to √x. A sieve (Algorithms chapter) is faster still.

Show solution

n = int(input())
primes = []
for x in range(2, n + 1):
    for p in primes:
        if p * p > x:
            primes.append(x)
            break
        if x % p == 0:
            break
    else:
        primes.append(x)
print(*primes)

Output

Answer