Generate Primes

Given a number n, return a list of all prime numbers smaller than or equal to n in ascending order.

Constraints

• n ≤ 100,000

https://binarysearch.com/problems/Generate-Primes

Examples

Example 1

Input

• n = 3

Output

• answer = [2, 3]

Example 2

Input

• n = 20

Output

• answer = [2, 3, 5, 7, 11, 13, 17, 19]

Example 3

Input

• n = 10

Output

• answer = [2, 3, 5, 7]

Solution