# 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?