Main content

## Computer science theory

### Course: Computer science theory > Unit 2

Lesson 6: Primality test- Introduction
- Primality test challenge
- Trial division
- What is computer memory?
- Algorithmic efficiency
- Level 3: Challenge
- Sieve of Eratosthenes
- Level 4: Sieve of Eratosthenes
- Primality test with sieve
- Level 5: Trial division using sieve
- The prime number theorem
- Prime density spiral
- Prime Gaps
- Time space tradeoff
- Summary (what's next?)

© 2023 Khan AcademyTerms of usePrivacy PolicyCookie Notice

# The prime number theorem

How can we estimate the number of primes up to x? Created by Brit Cruise.

## Want to join the conversation?

- The prime number theorem has an error rate, right? It doesn't give you the exact number of primes? How big does that error rate get? Is there ever a point at which the error rate is arbitrarily large, (meaning infinity)? Does it ever get large enough that the prime number theorem is useless for numbers past a certain point?(21 votes)
- Great question. Actually it's the opposite. The error rate is very large at first and decreases as you look towards infinity(34 votes)

- Is this the best known estimate of the number of primes less than a number? Are there better estimations?(6 votes)
- If you're really interested in primes, John Derbyshire wrote a book on the Prime Counting function called Prime Obsession. I read the book before I discovered Khan Academy, and I understood it pretty well, except for some of the material in the last chapter or two.(16 votes)

- Brit, what if the we don't plot the prime numbers 2-dimensionally

Isn't this just for human imagination ?

What if prime numbers lie in a fractional dimension like e.g. x²/³ or weirder ?(5 votes)- Well, if you were to try to assign a dimensional fraction to primes, it seems the dimension would have to decrease the larger the numbers were. This isn't like a traditional fractal which converges in some way to a measurable object. At least, not with any analogy I see.(4 votes)

- Some Fun Facts:

All 4 digit palindromic numbers are divisible by 11.

If we repeat a three-digit number twice, to form a six-digit number. The result will will be divisible by 7, 11 and 13, and dividing by all three will give your original three-digit number.

A number of form 2N has exactly N+1 divisors. For example 4 has 3 divisors, 1, 2 and 4.(6 votes)- (1 vote)

- The concept of infinity regarding primes is mentioned at0:33. When dealing with trigonometric functions, infinity also comes into play. Just as when one approaches the tangeant of 90 degrees (but exactly tan 90degrees or your calculator will register "error"), one approaches infinity. Could there then be a trigonometric solution to primes of the generation of prime numbers? Just a though that occured, particularly when you notice a flux in the intervals between prime numbers (ie. 2, 4, or 6 then back to 2 or 4).(4 votes)
- Really good idea, but there are two reasons this may not work.

1. There are an infinite number of primes, but those are 2 very different infinities. (blarghh 2 months of summer and I forget which is sin and which is tan :/) The number of primes is a counting infinity - there is an uncountable infinity of primes. tan90 is infinity, or error, because tan is opposite over adjacent. The 90 degree angle has 2 adjacent sides, so it a 90 degree angle does not actually have a tangent. We represent this with infinity, because Math says that every equation you can think of has to have an answer, which is why we invented imaginary numbers - because we could think of an equation, sqrt -1, that did not have a mathematical answer. tan90 also has no answer. Since 90 has no adjacent, we represent the adjacent as 0, so when you do opposite over adjacent, you get error or infinity. (depending on whether you're in Algebraic math or something more advanced that deals with hyperreals and stuff) So the first reason is because those are two very different kind of infinities - dividing by 0 infinities and uncountable existing infinities.

The second reason is because as the flux may work for the beginning of the Ulam Spiral, as you go further, the difference gets bigger and more uneven.(4 votes)

- Alas, there are more primes than I thought. What if I have a hard drive the size of the observable universe, where each atom represents a prime? The higher estimates of the number of atoms in the universe are around 10^83. I will be liberal and accept that. So, the formula is (#primes<x) ~ x/(ln(x)). So, 10^83~x/(ln(x)). I'm stuck. Since I hardly know the first thing about logarithms, can somebody show me approxiomately where the 10^83rd prime is?(2 votes)
- Its interesting the see the relationship. I realize that this video is found under the warm up section but what are the reasons that one would need to know how many prime number are in a trillion, or really any group of numbers? He mentions that accuracy is better the larger the number and that a trillion is a relatively small number, however in my thinking I would have no idea what to use a trillion numbers for.(2 votes)
- From a cryptography perspective, many ciphers (e.g. RSA) rely on our ability to secretly select random prime numbers within a certain range. In order for the randomly selected prime numbers to remain secret we need to make sure that there are enough prime numbers within the range to prevent an attacker from trying all the prime numbers within the range. In reality, the size of the primes being used are on the order of 2^512 to 2^1024, which is much much larger than a trillion. This is done to ensure that even the most dedicated and most powerful attacker would still be extremely unlikely to discover the secret prime number by brute force.

Summary: Attackers are trying to find a needle (our secret prime number) in a hay stack (the prime numbers in a certain range). We need to make sure that the hay stack is big enough to make it too hard for the attacker to find the needle. To make sure the hay stack is big enough it is useful to be able to estimate how big it is.

Hope this makes sense(5 votes)

- This is called the "Prime Number Theorem," yet as far as I know, there exist no formal proofs for such matters. Is this true, or am I mistaken?(3 votes)
- The prime number theorem was proven back in 1896. Since that time, several different proofs of it have been developed. Unfortunately, none of them are simple enough to describe here.

Here's a link to an article which talks about one of the more famous proofs by Erdos and Selberg:

http://www.cs.nyu.edu/spencer/erdosselberg.pdf

(It doesn't really describe the proof itself in detail. Instead, it describes the events surrounding the discovery of the proof)(1 vote)

- You just observed a finite number of primes and say that the formula will get closer to their actual number in infinity. How can you say that? Maybe there is a point at some really large number where it drops of. Can you explain, how the number of primes and the logarithm depend on each other and that this observation isn't just random?(2 votes)
- Here's a link to an "elementary" proof of the prime number theorem

http://math.uchicago.edu/~may/REU2013/REUPapers/Koenig.pdf

Unfortunately the proofs don't get much simpler than that (without understanding the field of complex analysis)(3 votes)

- I crave more videos on number theory, is this the only one yet?(2 votes)
- Here's some more:

https://www.khanacademy.org/math/recreational-math/math-warmup/number-theory-warmups/v/fermat-s-little-theorem-visualization

This one and the two that follow:

https://www.khanacademy.org/math/recreational-math/vi-hart/infinity/v/9-999-reasons-that-999-1

Here's some actual lectures on number theory:

https://www.youtube.com/watch?v=gfWf6vz8uaQ&list=PL8733118B95C1CFB5

Keep up the good work!(3 votes)

## Video transcript

Voiceover: Imagine we listed all
integers in a growing spiral, and colored the prime numbers blue, and left the composite numbers black. One interesting question we may ask is, "How many primes are there compared to composites?" First, let's zoom out
to see the big picture. Notice the prime color
is dense in the center, and slowly drops off in the distance but never seems to end. One way I like to think
about this is as follows: Imagine there is a tree at the center which is infinitely high. The leaves which drop from this tree represent prime numbers, which are scattered unpredictably below, dense near the base of the tree, and as we walk away from this tree, we find fewer leaves, though we always find them. This is exactly what happens when we look at larger
and larger integers. We always find more primes, though the number of primes
we find gradually drops, the further we look. So let's return to our question. How many primes are there
less than some integer x? If we make a table, we see the number of primes
is always increasing. Though as we search further, we find fewer and fewer. Let's graph the number of primes found on the vertical axis, and the search size x on the horizontal. As we zoom out to include
billions of numbers, notice the curve never flat lines. It's always rising, albeit gradually. First, let's think about
the density of primes less than some integer x. We can find the density by dividing the number of primes
found by the search size. For the first 100 integers,
we find 25 primes, therefore 25% are prime. Of the first 1000 integers,
we find 1229 primes, 12.29% are prime. Of the first 1 million
integers, 7.84% are prime. And the first 100 million
integers contain 5.76% prime. As we search further, this
density continues to drop, though the speed at which
it drops slows down. Here is a graph of the search size on the horizontal axis and the prime density on the vertical. Notice that as we zoom out, the primes are a vanishing
proportion of all integers. Amazingly, we find this formula in nature. We see it in galaxies, storms, flowers, and even inside our bodies as the design of least resistance, known as the logarithmic spiral. Notice that as the spiral rotates, it gets further and further
away from the center. Incredibly, the rotation
rate of a logarithmic spiral is related to the density
of primes as follows: We have the number of
rotations, call this phi. and the distance from
the center, call this r. If we graph phi against r, and zoom out, we see they are related according to the natural logarithm. This means the natural
logarithm of the distance is related to the number of rotations. The graph of the natural
logarithm is commonly written using the variable names y and x as y equals the natural logarithm of x. Notice the graph tapers
off in the same way the density of primes gradually decreases. The final step is to invert this by changing the y axis to 1 divided by the natural logarithm of x. And when we zoom out, we find the exact same curve generated when we plot the density of primes. Let's confirm this by
overlapping the two plots. In green, is a graph
of the line y equals 1 over the natural logarithm of x. And in red is the plot of prime number density up to x. As we zoom out, they approach each other. The further we zoom out, the more accurate the
green estimate becomes. This is known as the asymptotic law of
distribution of prime numbers. We now have a formula
to accurately tell us the density of primes without counting. The density of primes up to some integer x is approximately 1 divided by the natural logarithm of x or lawn x. So let's say you need to
know the density of primes between 1 and 100 trillion. Simple. 1 divided by lawn of 100
trillion equals 3.1%. Compare this to the actual result from counting all primes which is 3.2%. This is off by 0.1%. And as we check larger and larger numbers, the difference approaches zero. Realize now that we can use this formula for prime density to estimate the number of primes up to x. The number of primes is the area under the density curve for
which we can simplify by assuming density is constant. So number of primes
equals size times density or x divided by lawn x. This is the prime number theorem. Here is a graph of y equals
x divided by lawn x in blue, and in yellow, is a plot of
an actual count of primes. Notice as we zoom out, these lines eventually overlap
as we look to infinity. And that is it. We have a formula which
tells us approximately how many primes there are up to any value, no counting needed. For example, let's say we need to know the number of primes
less than 100 trillion. 100 trillion divided by the natural log of 100
trillion equals 3.1 trillion. Compare this to the actual count, which is 3.2 trillion. This is over 99.99% accurate even at this relatively small scale. So to recap: Given a search size up to some integer x, the prime density is
about 1 divided by lawn x And the number of primes is
about x divided by lawn x. This is the prime number theorem.