PythonMediumMath20 min

List all primes up to n

A prime has exactly two positive divisors. If n is less than two, print an empty line. Interviewers use this problem to assess mark multiples starting at each prime squared.

Input

One integer n.

Output

Print the result values separated by single spaces; print an empty line for an empty result.

Constraints

0 <= n <= 1000000.

Example

Input

Output

2 3 5 7 11 13 17 19

Example 2 input

Output

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

The square of a prime must be excluded.

Public test cases (2)

Input
```
20
```
Expected output
```
2 3 5 7 11 13 17 19
```
Input
```
10
```
Expected output
```
2 3 5 7
```

Hints (2)

Identify the state needed to avoid repeated work.
Mark multiples starting at each prime squared.

Target complexity: time O(n log log n) · space O(n)

Your solution

import sys


def solve_primes_up_to_n(n):
    # your code
    return []


if __name__ == "__main__":
    data = sys.stdin.read()
    n = int(data)
    result = solve_primes_up_to_n(n)
    print(" ".join(map(str, result)))

Standard input

Checking runner availability…

Reference solution

Check whether a number is prime · Easy
Check whether a string is a palindrome · Easy
Check whether two strings are anagrams · Easy
Compute the factorial of a number · Easy
Count vowels and consonants · Easy
Find the first occurrence with binary search · Easy
Find the missing number from zero through n · Easy
Find the second largest distinct value · Easy
Generate the Fibonacci series · Easy
Remove duplicate values while preserving order · Easy

All Python programs

List all primes up to n

Input

Output

Constraints

Example

Public test cases (2)

Your solution

Reference solution

More Python programs