The prime number theorem | Journey into cryptography | Computer Science | Khan Academy

Published by Darron Toy on

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.

Categories: ArticlesBlog


Yetoo · October 22, 2014 at 10:32 pm

This needs more attention.

Octav652 · January 19, 2015 at 8:24 pm

very interesting stuff

Google I/O 2019 · June 23, 2015 at 6:32 am


Ka'lika T. Fria'niquia · July 14, 2015 at 4:28 pm

'cum-POZZ-it' would be pretty chill. just sayin

Ka'lika T. Fria'niquia · July 14, 2015 at 4:38 pm

why is 'the natural logarithm of x' being vocalized as "Lon X"?

I looooooooooooooooove this topic. the info is well-presented.

but I swear – – math people talk weird sometimes.

David Russo · March 23, 2016 at 3:26 pm

You might be the only person alive who refers to the natural logarithm of x as "Lon X."

Phoenix · June 2, 2016 at 3:24 pm

e = Euler's number.

Sergio Fernandez · October 6, 2016 at 12:02 pm

I will be posting a video with my equation that will tell you if a
number is prime. the equation has also some other nice benefits.
Thanks everyone.

Tao Li · October 22, 2016 at 4:21 pm

Very clear explanations! Thanks!

Mustafa Ali · October 29, 2016 at 4:29 am

How did you realize that expansion?

Mohna Khan · March 5, 2017 at 4:04 pm

Well explained…

tomoka kazuki · April 2, 2017 at 11:02 pm

What happens if you combine prime numbers (the Huygens) with a chess game?

Suzana Michael · April 23, 2017 at 9:41 am

thank you so much

David Wilkie · April 26, 2017 at 9:31 am

(Observational conjecture): Pi might be called "two-ness" because it is an actual ratio of separation from one-ness prime and duality, rationally, and the natural logarithm reverses the process, continuously. The therom superimposed the forward and reverse process of coordinated connection. (?) IMO

I'm a total amateur but there seems to be millions of actual Mathematicians who could make a generalization of the idea? Ie, because primes and integers form related islands of consistency in a universe of natural logarithmic continuity, then there's a mathematical format for an hierarchical sequence of related constants (?) = "things as they are maybe"?

NOMAI · May 12, 2017 at 5:29 am

is anyone else here because of Seventeen?!

Poornakumar Das · July 13, 2017 at 4:14 pm

Thank you, a Lot !

Ryan Latterell · October 9, 2017 at 1:03 am

Is there a link to a video where the prime number theorem isnt a joke

Mohammad Sagor · November 1, 2017 at 12:17 am

this video should be nominated for oscar

quaily space · November 7, 2017 at 7:43 am

Hello, Khan Academy Labs. Also check out
「 Unknown and Simplest 」 Prime Numbers

Tadesan · December 28, 2017 at 3:59 am

Wow. Laaan x. Nice over-pronunciation…

Simple Harry371 · January 13, 2018 at 4:58 pm

Is this nonsense? What is the point?

David Hill · February 11, 2018 at 12:30 pm

You made a mistake saying 1229/1000 then showing 1229/10000

graviton · March 15, 2018 at 11:44 am

thanks……easy to understand…bravo.

Pharaoh on LFS · April 8, 2018 at 7:45 pm

Get off my ln()

엔에프카파비 · April 18, 2018 at 6:52 pm

진짜 신기하네

Sammeta naga srinivas · May 7, 2018 at 3:40 pm

so convincing

Arian Ashrafi · May 29, 2018 at 7:49 am

So what? What is the use of knowing how many prime numbers exist? I am not saying it is useless, but if this theory is useful at all it is better to mention it in the video.

Nikhil Nirmal · August 7, 2018 at 4:03 am

Must watch channel Nikhil Nirmal Prime numbers identification easily mention , ……

playgpgame · October 5, 2018 at 4:17 pm

Statement of Primality P = m -n, the operation with the lowest possible complexity level, aimed at the primality declaration of an unknown prime number P.

Ed Norton · October 8, 2018 at 1:09 am

Please keep in mind that some people , mostly males , are red green color blind.Hope this helps

Christopher Ellis · October 21, 2018 at 8:51 pm

That's 100 billion, chappy

Planet Watching · November 25, 2018 at 1:40 pm

Planet Watching · November 25, 2018 at 1:41 pm

The sine get larger so they will drop like a reverse harmonic. (Lo Janus)

Tezlashock · November 26, 2018 at 4:40 pm

Wouldn't this also work for finding how often the number 2 appears in the number line?

Orlando Vidads · December 3, 2018 at 9:55 pm

There might be a way of predicting prime numbers by creating columns of elimination. I have found something that seems to work and show a beautiful order to prime numbers I think I have found a way to determine every prime number at least to 1000. The method has not missed one number or given a superfluous number. But I am not really a mathematician. I am just a guy who likes to think about things.

Even numbers and multiples of 5 are easily eliminated. But what if there was a way to create other columns that could eliminate full large groups of numbers. First lets start with finding all of the possible prime number multiplles of 6 + or -1. And lets make our first column of elimination. For the numbers to fall in line properly, we take the prime number and multiply it times 6. For 5 that gives us thirty. So starting with 5 we add thirty to each row.

5 6 7 11 12 13 17 18 19 23 24 25 29 30 31
35 36 37 41 42 43 47 48 49 53 54 55 59 60 61
65 66 67 71 72 73 77 78 79 83 84 85 89 90 91
95 96 97 101 102 103 107 108 109 113 114 115 119 120 121
on so on. We eliminate all the columns of even numbers, plus the first column and the 2nd one created by the square of the prime.

Now we do the same process with 7. 7 x 6 is 42. So we will add 42 to 11 and each following row.
7 11 13 17 19 23 29 31 37 41 43 47
49 53 59 61 71 73 79 83 89
91 97 101 103 107 113 121 127 131
133 and so on. We eliminate all numbers from the Column of elimination after 7

We'll do the same with 11. 11 x 6 is 66. So will will add 66 to each row on the first column after 11
11 13 17 19 23 29 31 37 41 43 47 53 59 61 71 73
77 79 83 89 97 103 107 109 113 121 127 131 137 139
143 and so on, except we have another square prime that creates another column of elimination by adding 66: 121, 187, 253, 319

We'll do one more column. 13 x 6 is 78. So we will add 78 to each row after 13 and this will get us close to 100
13 17 19 23 29 31 37 41 43 47 53 59 61 71 73 79 83 89 97
91 97 101 103 107 109 113 119 131 137 139 149 151 157 161 167 and so on

17 x 6 is 102, so that column would eliminate 119 and 23 x 6 is 138 which would eliminate 161. All the remaining are prime numbers up to 167'
I have done this process up to 1021. There were no missed numbers and there were no extra numbers. There may have been about 10 duplicate numbers.

I think if this is what I think it might be I needed to share it and put it in the hands of people who would know what to do with it. I think one of the best parts about this is doing away with factoring which no one has ever enjoyed. I believe this show the true beauty and order that exists in prime numbers that we have never seen before.

I hope someone sees this. If not it will be in my next children's book about a boy who loves to count.

Psylife · January 14, 2019 at 11:10 pm

Everything simple is beautiful.

Ata Ayvacı · January 22, 2019 at 2:18 pm

Hi everybody, I am a high school math teacher and my main purpose is to make math easier. So all you need to do is subscribe to my channel.
Join my enjoyful lessons.

Graham Bond · February 1, 2019 at 2:52 am

The music of the Prime Numbers, part 4, Solution.

Йордан Панталеев · March 17, 2019 at 5:59 pm

5:05 "This is off by 0.1%" Actually this is off by about 3%. When using percent it always means proportion to the whole part. And whole part is just 0.032(proper way to write 3.2%), difference is 0.001, which is 3.125%.

A24 Leech Lattice · March 28, 2019 at 10:11 pm

Its crazy how the golden ratio shows up everywhere.

davinci84 · April 6, 2019 at 5:04 pm

Vert good explanation thank you

Algerian Culture and Traditions · June 17, 2019 at 8:36 pm

believe me, with a formula you can regenerate prime numbers such as
9431-9433-9437-9439 from the first

steve bob · August 12, 2019 at 2:25 pm


Dan -Horsenwelles- Williams · October 7, 2019 at 11:19 pm

so the spiral of prime numbers logarithmically results in a limit of pi% prime numbers inside any scaling area when the center is 0?

Mehmet Erkan Aktürk · November 18, 2019 at 8:57 pm

1:53 "of the first 1000 integers we find 1229 primes"


Jeffrey Bella · December 5, 2019 at 7:46 am

A~B =/= x(A) ~ x(B)

Ali Adams · December 31, 2019 at 11:35 am

Division is supposed to divide a number into smaller parts.
Dividing a number by 1 leaves it unchanged.
This is why divisibility by 1 must be removed from all definitions.

1 is indivisible. It is the Unit. [think PROTON]
A prime is a number that is divisible by itself only. [think ATOM]
A composite is a number that is divisible by itself and others. [think MOLECULE]

Please read
Good luck to all good people on Earth.
God > infinity

Leave a Reply

Your email address will not be published. Required fields are marked *