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:


We can improve the running time of is_prime
from O(n)
to O(sqrt(n))
:


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


Another implementation:


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 (1indexed)].
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 (1indexed). 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:

