# Find all prime numbers up to a given number

☰ Table of Content

# Problem Statement

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:

 ``````1 2 3 4 5 `````` ``````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))`:

 ``````1 2 3 4 `````` ``````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:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 `````` ``````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:

 `````` 1 2 3 4 5 6 7 8 9 10 11 `````` ``````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:

 ``````1 2 3 4 5 6 `````` ``````from math import factorial def numPrimeArrangements(n: int) -> int: primes = count_primes_less_than(n + 1) composites = n - primes return factorial(primes) * factorial(composites) ``````
Update: 2021-11-17