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?
What is computer memory?
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?