If you're seeing this message, it means we're having trouble loading external resources for Khan Academy.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Primality Test

2 articles
5 programs
8 videos
Why do primes make some problems fundamentally hard? To find out we need to explore primality tests in more detail.

Primality test challenge

How can a machine tell us if a number is prime?

Computer memory (space)

What is the limit of computer memory?

Algorithmic efficiency

How can we improve the speed of a (deterministic) primality test?

Level 3: Challenge

Try and improve the efficiency (time complexity) of you algorithm A so that it beats algorithm B in the worst case

Sieve of Eratosthenes

Sieve of Eratosthenes allows us to generate a list of primes.

Level 4: Sieve of Eratosthenes

Sieve of Eratosthenes

Primality test with sieve

An attempt at an optimal trial division primality test using the Sieve of Eratosthenes.

Level 5: Trial division using sieve

An attempt at an optimal trial division primality test using the Sieve of Eratosthenes.

The prime number theorem

How can we estimate the number of primes up to x?

Prime density spiral

Explore the distribution of primes

Prime Gaps

Graph of the spaces between prime numbers

Time space tradeoff

what is our memory limit? How can save time at the expense of space?

Summary (what's next?)

Why is factorization hard, yet generating primes easy? Where do we go from here?