Physicist: Primes are, for many purposes, basically random. It’s not easy to “find the next prime” or determine if a given number is prime, but there are tricks. Which trick depends on the size of the number. Some of the more obvious ones are things like “no even numbers (other than 2)” and “the last digit can’t be 5”; but those just eliminate possibilities instead of confirming them. Confirming that a number is prime is a lot more difficult.
Small (~10): The Sieve of Eratosthenes finds primes and also does a decent job demonstrating the “pattern” that they form.
Starting with 2, remove every multiple. The first blank is a new prime. Remove every multiple of that new prime. Repeat forever or until bored.
The integers come in 4 flavors: composites, primes, units (1 and -1), and zero. 2 is the first prime and every multiple of it is composite (because they have 2 as a factor). If you mark every multiple of 2, you’ll be marking only composite numbers. The first unmarked number is 3 (another prime), and every multiple of 3 is composite. Continue forever. This makes a “map” of all of the primes up to a given number (in the picture above it’s 120). Every composite number has at least one factor less than or equal to its square root, so if the largest number on your map is N, then you only need to check up to √N. After that, all of the remaining blanks are primes.
This algorithm is great for people (human beings as opposed to computers) because it rapidly finds lots of primes. However, like most by-hand algorithms it’s slow (by computer standards). You wouldn’t want to use it to check all the numbers up to, say, 450787.
Eratosthenes, in a completely unrelated project, accurately calculated the circumference of the Earth around 2200 years ago using nothing more than the Sun, a little trigonometry, and some dude willing to walk the ~900km between Alexandria and Syene. This marks one of the earliest recorded instances of grad student abuse.
Medium (~1010): Fermat’s Little Theorem or AKS.
Fermat’s little theorem (as opposed to Fermat’s theorem) works like this: if N is prime and A is any number such that 1<A< N, and if 
For a very long time (millennia) there was no way to verify with certainty that a number is prime in an efficient way. But in 2002 Primes is in P was published, which introduced AKS (Agrawal–Kayal–Saxena primality test) that can determine whether or not a number is prime with complete certainty. The time it takes for both FTL and AKS to work is determined by the log of N (which means they’re fast enough to be useful).
Stupid Big (~101010): Even if you have a fantastically fast technique for determining primality, you can render it useless by giving it a large enough number. The largest prime found to date (May 2014) is N = 257,885,161 − 1. At 17.4 million digits, this number is around ten times longer than the Lord of the Rings, and about twice as interesting as the Silmarillion.
Number of digits in the largest known prime vs. the year it was verified.
To check that a number this big is prime you need to pick the number carefully. The reason that 257,885,161 − 1 can be written so succinctly (just a power of two minus one) is that it’s one of the Mersenne primes, which have a couple nice properties that make them easy to check.
A Mersenne number is of the form Mn = 2n -1. Turns out that if n isn’t prime, then neither is Mn. Just like FLT there are false positives; for example M11 = 211 -1 = 23×89, which is clearly composite even though 11 is prime. Fortunately, there’s yet another cute trick. Create the sequence of numbers, Sk, defined recursively as Sk = (Sk-1)2 – 2 with S0 = 4. If 
With enough computer power this is a thing that can be done, but it typically requires more computing power than can reasonably be found in one place.
Update (Jan, 2016): The largest known prime is now 274,207,281 – 1.
Update (Jan, 2019): The largest known prime is now 282,589,933 – 1.
Answer Gravy: Fermat’s little theorem is pretty easy to use, but it helps to see an example. There’s a lot more of this sort of thing (including a derivation) over here.
Example: N=7 and A=2.
[27-1]7 = [26]7 = [64]7 = [64-9×7]7 = [64-63]7 = 1
So, 7 is mostly likely prime.
Example: N=9 and A=5.
[58-1]9 = [57]9 = [25x25x25x5]9 = [7x7x7x5]9 = [49×35]9 = [4×8]9 = [32]9 = 5
Astute readers will note that 5 is different from 1, so 9 is definitely not be prime.
For bigger numbers a wise nerd will typically exponentiate by squaring.
Example: N=457 and A=2. First, a bunch of squares:
![\begin{array}{ll}\left[2^2\right]_{457}=\left[4\right]_{457}\\\left[2^4\right]_{457}=\left[4^2\right]_{457}=\left[16\right]_{457}\\\left[2^8\right]_{457} =\left[16^2\right]_{457}=\left[256\right]_{457}\\\left[2^{16}\right]_{457}=\left[256^2\right]_{457}=\left[185\right]_{457}\\\left[2^{32}\right]_{457}=\left[185^2\right]_{457}=\left[407\right]_{457}\\\left[2^{64}\right]_{457}=\left[407^2\right]_{457}=\left[215\right]_{457}\\\left[2^{128}\right]_{457}=\left[215^2\right]_{457}=\left[68\right]_{457}\\\left[2^{256}\right]_{457}=\left[68^2\right]_{457}=\left[54\right]_{457}\end{array}](https://s0.wp.com/latex.php?latex=%5Cbegin%7Barray%7D%7Bll%7D%5Cleft%5B2%5E2%5Cright%5D_%7B457%7D%3D%5Cleft%5B4%5Cright%5D_%7B457%7D%5C%5C%5Cleft%5B2%5E4%5Cright%5D_%7B457%7D%3D%5Cleft%5B4%5E2%5Cright%5D_%7B457%7D%3D%5Cleft%5B16%5Cright%5D_%7B457%7D%5C%5C%5Cleft%5B2%5E8%5Cright%5D_%7B457%7D+%3D%5Cleft%5B16%5E2%5Cright%5D_%7B457%7D%3D%5Cleft%5B256%5Cright%5D_%7B457%7D%5C%5C%5Cleft%5B2%5E%7B16%7D%5Cright%5D_%7B457%7D%3D%5Cleft%5B256%5E2%5Cright%5D_%7B457%7D%3D%5Cleft%5B185%5Cright%5D_%7B457%7D%5C%5C%5Cleft%5B2%5E%7B32%7D%5Cright%5D_%7B457%7D%3D%5Cleft%5B185%5E2%5Cright%5D_%7B457%7D%3D%5Cleft%5B407%5Cright%5D_%7B457%7D%5C%5C%5Cleft%5B2%5E%7B64%7D%5Cright%5D_%7B457%7D%3D%5Cleft%5B407%5E2%5Cright%5D_%7B457%7D%3D%5Cleft%5B215%5Cright%5D_%7B457%7D%5C%5C%5Cleft%5B2%5E%7B128%7D%5Cright%5D_%7B457%7D%3D%5Cleft%5B215%5E2%5Cright%5D_%7B457%7D%3D%5Cleft%5B68%5Cright%5D_%7B457%7D%5C%5C%5Cleft%5B2%5E%7B256%7D%5Cright%5D_%7B457%7D%3D%5Cleft%5B68%5E2%5Cright%5D_%7B457%7D%3D%5Cleft%5B54%5Cright%5D_%7B457%7D%5Cend%7Barray%7D&bg=ffffff&fg=000000&s=0 "\begin{array}{ll}\left[2^2\right]_{457}=\left[4\right]_{457}\\\left[2^4\right]_{457}=\left[4^2\right]_{457}=\left[16\right]_{457}\\\left[2^8\right]_{457} =\left[16^2\right]_{457}=\left[256\right]_{457}\\\left[2^{16}\right]_{457}=\left[256^2\right]_{457}=\left[185\right]_{457}\\\left[2^{32}\right]_{457}=\left[185^2\right]_{457}=\left[407\right]_{457}\\\left[2^{64}\right]_{457}=\left[407^2\right]_{457}=\left[215\right]_{457}\\\left[2^{128}\right]_{457}=\left[215^2\right]_{457}=\left[68\right]_{457}\\\left[2^{256}\right]_{457}=\left[68^2\right]_{457}=\left[54\right]_{457}\end{array}")
As it happens, 457-1 = 456 = 256 + 128 + 64+8.
![\begin{array}{ll}\left[2^{456}\right]_{457}\\[2mm] =\left[2^{256}\cdot2^{128}\cdot2^{64}\cdot2^{8}\right]_{457}\\[2mm] =\left[54\cdot68\cdot215\cdot256\right]_{457}\\[2mm] =\left[202106880\right]_{457}\\[2mm] =1\end{array}](http://s0.wp.com/latex.php?latex=%5Cbegin%7Barray%7D%7Bll%7D%5Cleft%5B2%5E%7B456%7D%5Cright%5D_%7B457%7D%5C%5C%5B2mm%5D++%3D%5Cleft%5B2%5E%7B256%7D%5Ccdot2%5E%7B128%7D%5Ccdot2%5E%7B64%7D%5Ccdot2%5E%7B8%7D%5Cright%5D_%7B457%7D%5C%5C%5B2mm%5D++%3D%5Cleft%5B54%5Ccdot68%5Ccdot215%5Ccdot256%5Cright%5D_%7B457%7D%5C%5C%5B2mm%5D++%3D%5Cleft%5B202106880%5Cright%5D_%7B457%7D%5C%5C%5B2mm%5D++%3D1%5Cend%7Barray%7D&bg=ffffff&fg=000&s=0 "\begin{array}{ll}\left[2^{456}\right]_{457}\\[2mm] =\left[2^{256}\cdot2^{128}\cdot2^{64}\cdot2^{8}\right]_{457}\\[2mm] =\left[54\cdot68\cdot215\cdot256\right]_{457}\\[2mm] =\left[202106880\right]_{457}\\[2mm] =1\end{array}")
So 457 is very likely to be prime (it is). This can be verified with either some fancy algorithm or (more reasonably) by checking that it’s not divisible by any number up to √457.
Which makes it even more interesting is the way primes behave at ever bigger and bigger values. Bigger they become, the scarcer they will get, and still no proof of a so called “vanishing point”. I guess working with primes in clever ways is of the essence for cryptographers.
@Flavian Popa
If you’re interested, the prime number theorem describes how the density of primes decreases at higher values.
For numbers less than 2^64, in fact Miller-Rabin is all one needs for no false results, if the right bases are used. The relatively simple BPSW test also has been shown to have no false results below 2^64, and there are still no known counterexamples of any size. AKS was important for proving the problem is deterministic polynomial time, but the algorithm itself is very slow and not used in practice. We have other proof methods (ECPP and APR-CL) that are millions of times faster as well as showing better growth rates at any sizes we would be considering.
One interesting and constant-independent formula was “discovered” by C.P. Willans (the fifth formula).
http://mathworld.wolfram.com/PrimeFormulas.html
C’mon, Silmarillion is waaaaaaaay better than LoTR. The dude really knew how to make something sound epic.
I am interested in the connection between a useful(*) formula for the primes and the Riemann hypothesis (RH). I therefore have 2 questions.
1. Would a prove of RH indicate or even prove that a useful formula for the primes exists?
2. Would the existence of a useful formula prove the RH?
Any references would also be highly appreciated.
(*) By useful formula I am not necessarily referring to a calculation effective formula but rather a structural formula that shows the interconnection of the primes.
Prime numbers are like “axioms” for numbers, they form the basic building blocks of number, much like maths theorems derived from basic sets of logical axioms. Axioms are so-called facts that known to be TRUE but unprovable. Prime numbers are there but not “generatable”. If the fact that we can generate prime number from any forms of formulas means it’s no longer prime and hence, it can further generated from more basic “prime” numbers…
So, it would seems that most unsolvable mathematical theorem that deals with prime numbers may never able to be solved due to the basic nature of primes, as the Physicist says, are RANDOM.
While you can’t predict when the next prime number is, you can certainly create infinitely many prime numbers as you want.
for example, 2x3x5x7x11x13+1 is a prime number, even though I don’t know what that is.
so multiplying all the primes up to a certain point and adding one to the end always makes a new prime. Which is how you prove that there are infinitely many prime numbers.
2+1 = 3, a prime
2×3+1 = 7, a prime
2x3x5+1 = 31, a prime
2x3x5x7+1 = 211, a prime
@Carl Jalal
. 59 and 509 are both prime, and neither of them are 2, 3, 5, 7, 11, or 13.
What that technique does is generate numbers that always at least contains a prime that isn’t found in the original product. Sometimes that’s a new prime but, for example,
@Carl Jahal @Physicist
Could that formula be improved by subtracting the product of some of the chosen primes from the product of the rest of the primes? For instance, by arranging all of the primes up to some value as P*P*P*P . . . -P*P*P . . . . so that the result is less than the largest of these primes squared?
The sequence {15 (n!!)/ 2n+1} appears to return either a whole number, or an irreducible fraction with a prime in the denominator, which remains 2n + 1 if 2n + 1 is prime, for n > 2.
I have no proof, so maybe there is a composite number the thing doesn’t eat.
Why is 2^(2^57,885,161 – 1) – 1 not the largest Mersenne prime number??
How do prime numbers relate to nature? Example? (E.g. Fibonacci series is related with spirals that occur in nature/life.)
“Physicist: Primes are, for many purposes, basically random.”
Absolutely not.
Fully deterministic algorithm for finding prime numbers:
Positive integers not contained in both 2-dimensional arrays
P1(i,j)=6i^2-1+(6i-1)(j-1) and P2(i,j)=6i^2-1+(6i+1)(j-1)
are indexes p of primes in the sequence S1(p)=6p+5, p=0,1,2,…;
Positive integers not contained in both 2-dimensional arrays
P3(i,j)=6i^2-2i-1+(6i-1)(j-1) and P4(i,j)=6i^2+2i-1+(6i+1)(j-1)
See: http://ijmcr.in/index.php/archive/41-volume-3-issue-3-march-2015/86-title-matrix-sieve-new-algorithm-for-finding-prime-numbers
are indexes p of primes in the sequence S2(p)=6p+7, p=0,1,2,…;
Do you know any attempted prime number formulas that failed? It would help me a lot in my search for creating a formula that generates only primes.
P.S. To everybody: if any of you think there is already a formula for that, There isn’t. The closest are the failed formulas and the formula that either generates a number that is a multiple of a new prime number or a prime number.
There are two 2-dimensional arrays:
……………………………|5 10 15 20 ..|
6i^2-1+(6i-1)(j-1)= |23 34 45 56…|
……………………………|53 70 87 104…|
……………………………|95 118 141 164…|
……………………………|149 178 207 236…|
……………………………|… … … … |
…………………………….| 5 12 19 26 ..|
6i^2-1+(6i+1)(j-1)= |23 36 49 62..|
…………………………….|53 72 91 110…|
…………………………….|95 120 145 170…|
……………………………..|149 180 211 242..|
…………………………….|… … … … |
Positive integers not contained in these arrays are indexes p of all prime numbers in the sequence S1(p)=6p+5
, i.e. p=0, 1, 2, 3, 4, , 6, 7, 8, 9, , 11, , 13, 14, , 16, 17, 18, , , 21, 22, , 24, , , 27, 28, 29, …
and primes are: 5, 11, 17. 23, 29, , 41, 47, 53, 59, , 71, , 83, 89, , 101, 107, 113, , , 131, 137, , 149, , , 167, 173, 179, ….
There are two 2-dimensional arrays:
………………………………..| 3 8 13 18 ..|
6i^2-1-2i+(6i-1)(j-1)= | 19 30 41 52…|
………………………………..| 47 64 81 98…|
………………………………..| 87 110 133 156…|
………………………………..|139 168 197 226..|
………………………………..|… … … … |
………………………………….| 7 14 21 28 ..|
6i^2-1+2i+(6i+1)(j-1)= |27 40 53 66…|
………………………………….|59 78 97 116..|
………………………………….|103 128 153 178…|
………………………………….|159 190 221 252…|
………………………………….|… … … … |
Positive integers not contained in these arrays are indexes p of all prime numbers in the sequence S2(p)=6p+7, i.e. p=0, 1, 2, , 4, 5, 6, , , 9, 10, 11, 12, , , 15 , 16, 17, , , 20, , 22, , 24, 25 , 26, , , 29, …
and primes are: 7, 13, 19. , 31, 37, 43, , , 61, 67, 73, 79, , , 97, 103, 109, , , 127, , 139, , 151, 157, 163, , , 181 ….
http://www.planet-source-code.com/vb/scripts/ShowCode.asp?txtCodeId=13752&lngWId=3
What is a prime?
¿Qué es un número prime?
Prime numbers (primes) – integers divisible only by 1 and themselves.
New largest prime announced today. (2^74,207,281)-1. http://www.mersenne.org/primes/
Prime numbers?
Is there a formula for greatest prime factor of n? I’m not referring to the golden goose here, just a formula, summation or otherwise. But, a formula either way. I’m specifically interested in one that does not include other prime formulas such as the prime counting formula. Just a formula in n, maybe including an index of summation if its a sum. I don’t care if it is efficient or not. It just has to equal gpf(n).
I’m afraid, such a formula does not exist
Interesting. I have one, and several other formulas for prime functions in number theory, all very simple and easily provable. However, I am self taught and have no connections within academia and so I find it impossible to even post a paper. I am ready to share my work with the world. I haven’t the slightest idea how unfortunately. Perhaps we can begin a correspondence. You would be the first to see some of my work and actually understand it. I offer a real and new mathematical body of work with no crackpot or extreme amateur material to waste your time. This seemed as good a place as any. Please email me.
Thank You .
I’m interesting in number theory and I have proposed so called “matrix sieve” , which for my vew is the simplest algorithm for finding primes ( see: comment above and http://www.planet-source-code.com/vb/scripts/ShowCode.asp?txtCodeId=13752&lngWId=3).
My email: brs.sklr@mail.ru
Dear Anthony Browne,
if you like please send me your results! I am interested to have a look, even I am a Physicist. Best, N
Euler was wrong
“Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers and we have reason to believe that it is a mystery into which the mind will never penetrate”
https://www.academia.edu/24889811/Constantine_Adraktas_-_The_Prime_numbers_are_not_random_…_so_what_happens_now_to_Cryptography_
If I found a programm or formula for prime number what shall I do with it and is it something worth, althoug i did not find solution for riemann or goldbach questions. The formula is about 4 rows.
with kind regards
Udo Krampe
It is now available in English my algebraic proof of the non-existence of a law for prime numbers : tesisuinumeriprimi.blogspot.it
(The paradoxical randomness of prime numbers: an informal introduction.)
Hello,
I would like to explain the Prime Locomotive. The locomotive runs on the tracks, the numbers are the ties. The locomotive starts at #1 and finds no number, there so it places the #1 into the prime folder. It then moves on to tie #2 and finds no number there also, so it places #2 into the prime folder, then multiplies the #2 tie down the tracks to place numbers at all even numbered ties. Then the locomotive moves to tie #3 location, finds nothing and places #3 into the prime folder and multiplies 3 down the tracks to put a number at all locations that are multiples of 3. Then on to tie #4, finds a number there so it cannot be a prime, and moves on to tie #5. Finding nothing at tie #5 it places #5 in the prime folder and multiplies 5 down the tracks. As the locomotive travels eternally down the tracks it periodically comes across empty tie locations and places those numbers in the prime folder. Regards, Russell Lee
Prime Number Theory Postulated Using Set Theory
N = P + nP, where N (all natural whole numbers) equals P (all Primes) plus nP (all non-Primes).
P = N – nP, where P (all primes) equals N (all natural whole numbers) minus nP (all non-Primes).
P = N – {2(N + 1)} – {3(2N + 1)} – {(6N-1)((6N-1) + (12N-1) + (18N-1) + (24N-1)+ …(6(∞)N-1))}
– {(6N+1)((6N-1) + (12N-1) + (18N-1) + (24N-1)+ …(6(∞)N-1))}
– {(6N+1)((6N+1) + (12N+1) + (18N+1) + (24N+1)+…(6(∞)N+1))} ,
where P is all primes, nP is all non-primes, N is all natural whole numbers, and P≠ 0,1.
Disribution of primes is determined by the following THEOREM (without any kind of randomness):
Odd integer N=6p+5 is a prime number if and only if no one of two diophantine equations
6x^2−1+(6x−1)y=p
6x^2−1+(6x+1)y=p
has solution.
Odd integer N=6p+7 is a prime number if and only if no one of two diophantine equations
6x^2−1−2x+(6 −1)y=p
6x^2−1+2x+(6x+1)y=p
has solution.
x=1,2,3,..y=0,1,2,…p=0,1,2,..
From this THEOREM we can show that:
a) All prime numbers (exept 2 and 3) belong to two sequences
S1(p)=6p+5 and S2(p)=6p+7;
b) Ratio of number of primes in the sequence S1(p) to number of primes in the sequence S2(p)
tends to be 1.
c) Positive integers which do not appear in two 2-dimentional arrays
P1(i,j)=6i^2-1+(6i-1)(j-1)
P2(i,j)=6i^2-1+(6i+1)(j-1), i,j=1, 2, 3,…
are indexes p of primes in the sequence S1(p)=6p+5..
Positive integers which do not appear in two 2-dimentional arrays
P3(i,j)=6i^2-1-2i+(6i-1)(j-1)
P4(i,j)=6i^2-1+2i+(6i+1)(j-1), i,j=1, 2, 3,…
are indexes p of primes in the sequence S2(p).
thank you for share great information related to prime number. i found best prime number formula https://www.andlearning.org/prime-number-formula/ you can also check better for knowledge
For what it’s worth (and much / all? has been stated / shown before in some form) I believe this simple method eliminates all non-prime numbers; even #s, all #s divisible by 5 (ends in 5 or 0), all #s where the sum of the digits are divisible by 3, and 7 squared, to third power, fourth power, etc. However, it is non-predictive, and proves /eliminates only what isn’t a prime number. I theorize though, that a number larger than the known highest prime that isn’t eliminated using the above method would be the new highest prime. I wish I had the time and intelligence to pursue further.
If one looks at charts of primes using base ten, then there are no obvious patterns of primes. However if one looks at charts of primes using base six, the patterns become basically obvious.
Using set theory:
N = P + nP, where N (all natural whole numbers) equals P (all Primes) plus nP (all non-Primes).
P = N – nP, where P (all primes) equals N (all natural whole numbers) minus nP (all non-Primes).
P = N – {2(N + 1)} – {3(2N + 1)} – {(6N-1)((6N-1) + (12N-1) + (18N-1) + (24N-1)+ …(6(∞)N-1))}
– {(6N+1)((6N-1) + (12N-1) + (18N-1) + (24N-1)+ …(6(∞)N-1))}
– {(6N+1)((6N+1) + (12N+1) + (18N+1) + (24N+1)+…(6(∞)N+1))} ,
where P is all primes, nP is all non-primes, N is all natural whole numbers, and P≠ 0,1.
If you email me I’ll send you the charts I’ve developed (which are not reproducible here in this format.
in 1983, Mr. A. Venugopalan published a paper in the Proceedings of Indian Academy of Sciences. One of the formulas was to generate ONLY prime numbers. In other words, it gives the nth prime. The proof is accompanied in that research paper.
There is formula to find composite numbers here https://www.researchgate.net/publication/339140973_SUBLINEAR_SEGMENTED_PRIME_SIEVE
https://math.stackexchange.com/questions/3037819/the-prime-number-matrix-sieve#
what about (N*2-1)*(N*2-1) – 2 ?
does that work?