# Find all prime numbers up to a given number

## Problem Statement

How do we find all the prime numbers up to a given number?

For example, when `n = 10`

, the output should be `4`

since there are 4 prime numbers less than 10, namely 2, 3, 5, 7.

## Naive Approach

A naive approach would be to iterate from `2`

to `n`

and count the number of primes along the way:

```
def count_primes_less_than(n: int) -> int:
return sum(is_prime(i) for i in range(2, n))
def is_prime(num: int) -> bool:
return all(num % i != 0 for i in range(2, num))
```

We can improve the running time of `is_prime`

from `O(n)`

to `O(sqrt(n))`

:

```
from math import sqrt
def is_prime(num: int) -> bool:
return all(num % i != 0 for i in range(2, int(sqrt(num)) + 1))
```

## Sieve of Eratosthenes

An efficient approach is called Sieve of Eratosthenes. Below is a Python implementation:

```
from math import sqrt
def count_primes_less_than(n: int) -> int:
nums = [True] * n
ans = 0
for i in range(2, n):
if nums[i]:
ans += 1
nums[i] = False
for j in range(i * i, n, i):
nums[j] = False
return ans
```

Another implementation:

```
from math import sqrt
def count_primes_less_than(n: int) -> int:
if n < 2:
return 0
composites = set()
for i in range(2, int(sqrt(n)) + 1):
if i not in composites:
for j in range(i * i, n, i):
composites.add(j)
return n - len(composites) - 2
```

## Prime Arrangements

Now that we know how to efficiently find the number of primes less than a given integer, let’s count the number of permutations of 1 to n so that prime numbers are at prime indices (1-indexed)].

For example, when `n=9`

, we want primes <= 9 to be at indices 2, 3, 5, 7 and composites at indices 1, 4, 6, 8, 9 (1-indexed). We can place primes <= 9 at indices 2, 3, 5, 7 in `4! = 24`

ways. We can place composites <= 9 at indices 1, 4, 6, 8, 9 in `5! = 120`

ways.

In general, the prime arrangement count equals the number of permutations of the primes multipled by the number of permutations of the composites:

```
from math import factorial
def numPrimeArrangements(n: int) -> int:
primes = count_primes_less_than(n + 1)
composites = n - primes
return factorial(primes) * factorial(composites)
```