This calculator finds prime numbers
and you can check numbers for several conjectures
about primes.
You can also find all the divisors (factors) of a number or find the largest single divisor of a set of
numbers (gcd)
or the smallest number which has every number in the list as a divisor (lcm).
Numbers must be positive and are limited to the Javascript range of up to 16 digits ≈ 9×1015 or, more precisely,
whole numbers ≤ 9007199254740991 = 253−1.
On this page, prime numbers are shown like this.
Semiprimes
A semiprime is a number n that has just 2 prime factors p and q
so n = p × q. It is therefore "almost" a prime
(which has only one prime factor, itself!) or a semiprime.
They have two useful applications:
Encryption
Special algorithms are used to encode a transaction at a cash machine or anything that has to send important information over
a public network (such as a phone line or internet connection) where we need a secure connection.
RSA and other public-key cryptosystems use a VERY large semiprime. The sender
and receiver at either end know one of two prime factors of the semiprime and so can work out the other and knowing both prime factors
is essential to decoding the message.
If anyone intercepts the message and even if they know the semiprime but do not know the two prime factors then there is no
way they can decode the message. This is because no one yet knows any
fast and efficient method for finding the two prime factors of very large semiprimes.
Knowing both of the two large prime factors is absolutely essential to decoding the message in such systems so semiprimes play an important role
everyday when you use a credit card or draw money out of a cash machine.
The unique size of a rectangle
In 1974 a message was beamed from the Arecibo radio telescope into space towards a galaxy 25000 light years away
with the hope that an alien culture there might one day receive it and understand it.
It was a stream of 1679 bits (0s and 1s).
Why 1679?
Because 1679 is a semiprime: 1679 = 23 × 73
so there is just one rectangular shape into which we can fit the 1679 bits.
If we represent 1s as black dots and 0s as white dots
we get the rectangular "picture" on the right of 73 rows and 23 columns.
However, a rectangle of 23 rows of 73 columns
is not the same as a rectangle of 73 rows of 23 columns and gives a completely different arrangement of the bits!
Use the button to see the other version (the bits go down the columns instead of across the rows first).
If our intelligent aliens manage to "see" this "picture" and not the other arrangement, then would they interpret it as it was meant
to be "read"? I seriously doubt it!
It seems to have more to say about the state of computer graphics in the early 1970's than it does
about the intelligent humans that sent it, but see what you think....
Have a go yourself at interpreting the "picture"
before looking up the intended meanings at revolvy.com.
The Conjectures
These are statements about all numbers of a certain kind but they are conjectures or "open" statements
because there is neither a proof that they are always true or a proof that they are not always true.
Perhaps you can find a pattern that you can prove always holds or perhaps you can find an example which shows it is not true
for a particular number (a counter-example)?
Goldbach's conjecture
(as adapted by Euler) is that
every even number ≥4 is the sum of 2 prime numbers and has been verified up to 4×1018
but there is as yet no proof. An odd number is the sum of two other odd numbers so our primes here are the odd ones
and exclude 2.
This calculator will therefore not find a counter-example (which would prove the conjecture is false)
but you can use it to spot patterns which is one way to approach finding a proof that it true.
For example:
is that all odd numbers≥9 are the sum of three odd primes
This would automatically be true if the (strong) Goldbach conjecture above was true.
How? Because we can take 3 (a prime) from any odd number and the even number
remaining would be sum of 2 primes IF the (strong) Goldbach conjecture was true. So the odd number is a sum of 3 odd primes.
For example:
But we do no know if the Goldbach conjecture is true and neither is a proof or disproof of this weaker form.
Lemoine's conjecture (sometimes called Levy's conjecture)
is that all odd numbers >6 are the sum of a prime number and twice a prime number.
For example:
39 = 29 + 2×5
41 = 37 + 2×2
43 = 37 + 2×3
It has been verified up to 109 so there is a possibility that you could find a counter-example using this Calculator!
Oppermann's Conjecture
is about the distribution of primes - another mystery that mathematicians do not fully understand.
The conjecture from 1882 is that within a range of n numbers either side of n2 there is always at least one prime number.
More formally: There is always a prime number in the range N2 − N .. N2 and in the range N2 .. N2 + N
for every number N>1.
For example, if N is 5 then the lower range is 20..25 which contains the prime 23 and in the range 25..30 there is a prime: 29.
Often, of course, there is more than one but Oppermann's conjecture is there is always at least 1.
The number of primes between N2−N and N2 for N≥2 is
2, 1, 1, 1, 1, 2, 2, 2, 1, 1, 2, ... A094189
The number of primes between N2 and N2+N is 1, 1, 1, 2, 1, 2, 1, 2, ... A089610
Legendre's Conjecture
is that there is always a prime between two neighbouring square numbers, that is between N2 and (N+1)2
but since N2+N < (N+1)2 = N2 + 2N + 1
then Oppermann's conjecture if proved true would immediately show that Legendre's conjecture is true also.
However there is no proof of either as yet.
The Twin Primes conjecture
The prime numbers begin 2, 3, 5, 7, 11, 13, 17, 19, 29, 31, ...
and we notice that, after 2 and 3, there are several pairs here that have the minimum difference of 2, called "twin primes":
3,5; 5,7; 11,13; 17,19; 29,31; ... ; A001359,A006512.
Alternatively, we can find numbers n where n±1 are both prime. This list is 4, 6, 12, 18, 30, ..., A014574
and all entries after the first are multiples of 6.
The Twin Primes Conjecture is that there are infinitely many pairs of primes p and p+2.
Many records have been broken recently in looking for "the largest known twin primes".
In September 2016 it was proved that
2996863034895 × 21290000 ±1 were both prime and they have 388342 digits!
On 19 October 1994, Thomas Nicely, a professor of mathematics at Lynchburg College in Virginia USA,
in the course of establishing that there are 135780321665 twin primes less than 1014
notoriously revealed an error in the Pentium computer chip's Floating Point Unit. It was
corrected in later verisons of the chip.
Most mathematicians would suspect the list never ends, but there is no proof yet.
Output format:
Prime factors are shown as primes-with-powers
e.g. 24 = 23 × 3
Input range:
For just one number, leave the up to box empty.
To perform the same calculation on each number in a range of numbers,
give the starting number N box and the highest in the up to box.
Number format:
Enter a number up to 16 digits
or an expression using the following:
Operations:
+ - * /
Constants:
E =2.71828..., PI=3.14159..., Phi=1.61803..., phi=0.61803..,
MAXINT=9007199254740991 is the largest integer this calculator can use.
Functions:
for numpower use pow(num,power)
abs(real) to ignore sign, round(x) to nearest integers; floor(x) round down; sqrt(x) for √x
mod(a,b) for remainder of a÷b, powmod(x,pow,m) for mod( xpow, m)
sin, cos, tan, asin, acos, atan with radian argument
exp(x) for Ex, log(x) for natural log, log10 for base 10 log, logB(base,x)
gcd(a,b), lcm(a,b), EulerPhi(n) for Euler's totient function φ(n)
Factors and Divisors
The calculator can factor a number into primes and also count or list all the factors of N.
Another function that turns out to be very useful in Number Theory is the count of those numbers
less than N which are not factors and share no common factor with it, called the
(Euler) totient function and written φ(N) and pronounced "phi of N".
For instance the prime factorisation of 12 is 22×3
12 has 6 factors: 1,2,3,4,6,12 and
there are 4 smaller numbers that are co-prime to 12: 1,5,7,11 so φ(12) = 4.
These four are all the numbers 1≤i≤N where gcd(i,12)=1
Primes:
check if it is a prime number i.e. it has no factors except itself and 1
e.g 13 is prime but 14 is not
find the nearest prime above and below a given number
e.g. on either side of 1 000 000
there are the primes 999983 and 1000003
check Goldbach's conjecture which says that every even number is the sum of
two odd prime numbers
e.g. 100 is the sum of the two odd primes 3
and 97
Factors:
Show all prime factors, for example:
336 is the product of primes 24×3×7
337 = 337 because it is prime
show all divisors (factors) for example:
14 has 4 factors: 1,2,7,14
count the smaller numbers which have no factor in common with N (numbers which are co-prime to N)
written as φ(N)
e.g. 14 has 6 smaller co-prime numbers
because the 6 numbers 3, 5, 7, 9, 11, and 13 have no factor in common with 14
gcd, lcm
greatest common divisors (gcd, also called hcf)
gcd of a list of numbers (at least two), separated by commas:
enter the numbers in the box each separated by a comma e.g. 16, 40, 24
lowest common multiple (lcm)
lcm of a list of numbers (at least two) each separated by a comma
e.g. lcm(12,15) = 60
because there is no smaller number than 60 which has both 12 and 15 as divisors
The Primes and Factors Calculator
C A L C U L A T O R
Calculating...
Range:
N
up to
Primes
with difference =
Factors
of
R E S U L T S
Prime numbers are shown like this
Further investigations
Lemoine's Conjecture
In how many ways can we write n, an odd number, as n = p + 2 q
for prime numbers p and q?
The number of ways to satisfy Lemoine's conjecture
:n<200
:n<2000
:n<20000
Show counts for n≡3(mod 6) in red, n<20000
The counts of the number of solutions for 1,3,5,7,... (the odd numbers) is
0, 0, 0, 1, 2, 2, 2, 2, 4, 2, 3, 3, 3, 4, ... A046927
and, if the conjecture is true, then there should be no further zeroes in the sequence apart from the first three (n<7).
A graph of the number of solutions of Lemoine's Conjecture for odd numbers up to 6000,
is shown here.
It has an interesting structure that invites further exploration.
If we plot in red the counts for the (odd) numbers leaving a remainder of 3 when divided by 6 and
the others in blue, the split in the plot reveals one of its secrets.
7 is the first (odd) number with a solution: 7 = 3 + 2×2
9 is the first number with 2 solutions: 9 = 3 + 2×3 = 5 + 2×2
17 is the next with not 3 but 4 solutions: 17 = 3+2×7 = 7+2×5 = 11+2×3 = 13+2×2.
Continuing this list, the numbers that break records (they have more solutions than any earlier value) are
7, 9, 17, 33, 45, 51, 75, ... A194830:
Levy's Conjecture
Levy's conjecture of 1963 (see the reference below) is just Lemoine's but he also adds
that if we can write the odd number 2N + 1 as 2P + Q for primes P and Q then he conjectures there is a Q
in the range 1<Q<(2N + 1)/3.
This is clearly false even for small N. It fails for 2N+1 = (3, 5,) 7, 9, 11, 15, 21, 23, 35, 83, ... .
For example:
7 = 3 + 2×2 but 3 exceeds 7/3
35 = 13 + 2×11 = 29 + 2×3 = 31 + 2×2
and again 13 exceeds 33/3.
However, if Levy meant P (the prime that is doubled) instead of Q, then it is an excellent conjecture and is almost certainly true for all odd numbers from 7 onwards.
At the foot of page 434 Dickson states that E Lemoine conjectured ("stated empirically") that every odd number bigger than 3 is the
sum of a prime number and the double of a prime. The full reference is:
Émile Lemoine in L'intermédiaire des mathématiciens vol 1 (1894) page 179 and vol 3 (1896) page 151.
Lemoine also conjectures that all odd numbers can also be expressed as a prime minus double a prime and also
as double a prime minus a prime.
Letter to the Editor 30 March 1963 from Hyman Levy, Math.Gaz. (vol 47, 1963) page 274 JSTOR Levy mentions Lemoine's conjecture but not by name and offers another conjecture about one of the primes.
OEIS A046927 the number of ways to write an odd number as p+2q, for primes
p and q. If Lemoine's conjecture is true then all entries from the 4th onwards are bigger than 0.
Unsolved Problems in Number Theory (3rd edition 2004) by R Guy, Springer
has a whole set of chapters on conjectures about primes. Section A8 is about gaps between primes and the Twin Prime conjecture.
It also has many references to recent results.
Introduction to the Theory of numbers by G H Hardy and E M Wright
Oxford University Press, (6th edition, 2008)
is the classic mathematics book on Number Theory. It has a full and rigorous treatment of primes and related subjects
and, though it is definitely at university undergraduate level, it still is a very valuable reference of theorems and proofs.