If you're seeing this message, it means we're having trouble loading external resources on our website.

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

# 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? •  Great question. Actually it's the opposite. The error rate is very large at first and decreases as you look towards infinity
• Is this the best known estimate of the number of primes less than a number? Are there better estimations? • 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.
• 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 ? • 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. • The concept of infinity regarding primes is mentioned at . 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). • 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.
• 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? • 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. • 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   