Skip to main content
ponderloop

Prime Number Checker

7,919 is prime: no whole number from 2 to 88 divides it exactly, so its only divisors are 1 and itself. It is the 1,000th prime, between the primes 7,907 and 7,927. Type any whole number up to 3,317,044,064,679,887,385,961,980 (about 3.3 × 10^24) for an exact answer with its nearest primes, or switch to the primes in a range with their twin pairs, or the count of primes up to N.

Updated Runs in your browser: nothing you enter is uploadedHow this tool works

A whole number from 0 up to 3,317,044,064,679,887,385,961,980 (about 3.3 × 10^24). Commas are fine.

What to find

Is 7,919 prime?

7,919 is prime

7,919 has no divisor other than 1 and itself; it is the 1,000th prime. The nearest primes are 7,907 and 7,927.

The primes around 7,919

7,883, 7,901, 7,907, 7,919, 7,927, 7,933, 7,937

Number
7,919
Prime or composite
Prime
Method
Trial division by 2, 3 and 6k ± 1 up to 88
Previous prime
7,907 (12 below)
Next prime
7,927 (8 above)
Position among the primes
1,000th prime

The working

  1. Every composite number has a prime factor no larger than its square root, so trying divisors up to 88 is enough (88² = 7,744 ≤ 7,919 < 7,921).
  2. Try 2, then 3, then only the numbers 6k − 1 and 6k + 1 (5, 7, 11, 13, 17, 19, …): every prime above 3 has that form, so nothing else needs testing.
  3. None of them divides 7,919 exactly, so 7,919 is prime.
  4. Neighbours: testing the odd numbers down from 7,918 and up from 7,920 with the same test gives the previous prime 7,907 and the next prime 7,927.

The first 100 prime numbers

Found by the checker’s own sieve of Eratosthenes: the primes in order, ten to a row. The 100th prime is the last one in the table.
PositionsPrimes
1st to 10th2, 3, 5, 7, 11, 13, 17, 19, 23, 29
11th to 20th31, 37, 41, 43, 47, 53, 59, 61, 67, 71
21st to 30th73, 79, 83, 89, 97, 101, 103, 107, 109, 113
31st to 40th127, 131, 137, 139, 149, 151, 157, 163, 167, 173
41st to 50th179, 181, 191, 193, 197, 199, 211, 223, 227, 229
51st to 60th233, 239, 241, 251, 257, 263, 269, 271, 277, 281
61st to 70th283, 293, 307, 311, 313, 317, 331, 337, 347, 349
71st to 80th353, 359, 367, 373, 379, 383, 389, 397, 401, 409
81st to 90th419, 421, 431, 433, 439, 443, 449, 457, 461, 463
91st to 100th467, 479, 487, 491, 499, 503, 509, 521, 523, 541

How many primes there are up to 10, 100, 1,000 … 10,000,000

Every row is the checker’s own count by sieve: π(x) is the number of primes up to x. The last two columns compare it with the estimate x ÷ ln x (floating point, rounded) and count the twin prime pairs.
xπ(x), the primes up to xShare of 1 to x that is primex ÷ ln xπ(x) ÷ (x ÷ ln x)Twin prime pairs up to x
10440.00%40.9212
1002525.00%221.1518
1,00016816.80%1451.16135
10,0001,22912.29%1,0861.132205
100,0009,5929.59%8,6861.1041,224
1,000,00078,4987.85%72,3821.0848,169
10,000,000664,5796.65%620,4211.07158,980

Primes in each block of 100 numbers, up to 1,000

Each row is the checker’s range answer for its block. Twin pairs count only pairs that lie inside the block; the share of primes thins out as the numbers grow.
NumbersPrimesTwin prime pairsWidest gapShare that is prime
1 to 1002588 (89 to 97)25.00%
101 to 20021714 (113 to 127)21.00%
201 to 30016412 (211 to 223)16.00%
301 to 40016214 (317 to 331)16.00%
401 to 50017312 (467 to 479)17.00%
501 to 60014218 (523 to 541)14.00%
601 to 70016312 (619 to 631)16.00%
701 to 80014014 (773 to 787)14.00%
801 to 90015514 (839 to 853)15.00%
901 to 1,00014014 (953 to 967)14.00%

Worked examples: eight numbers, tested

Each row is the checker’s own answer: the verdict, the method it used and the evidence, with the primes either side of the number.
NumberVerdictMethodEvidencePrevious and next prime
1Neither prime nor compositeBy definitionOnly one factornone and 2
91CompositeTrial divisionDivisible by 789 and 97
561CompositeTrial divisionDivisible by 3557 and 563
7,919PrimeTrial divisionNo divisor up to 887,907 and 7,927
2,147,483,647PrimeTrial divisionNo divisor up to 46,3402,147,483,629 and 2,147,483,659
1,000,000,000,039PrimeMiller-Rabin, 5 basesAll 5 bases pass999,999,999,989 and 1,000,000,000,061
147,573,952,589,676,412,927CompositeMiller-Rabin, 12 basesBase 3 is a witness; no factor below 1,000,000147,573,952,589,676,412,909 and 147,573,952,589,676,412,931
1,000,000,000,000,000,000,000,007PrimeMiller-Rabin, 13 basesAll 13 bases pass999,999,999,999,999,999,999,743 and 1,000,000,000,000,000,000,000,049

How many Miller-Rabin bases prove a number prime

The bases are the first primes. For every number below the threshold, the test with that many bases cannot be fooled; this is the list the checker uses (published results, listed in the sources).
Numbers belowBases usedNumber of bases
2,04721
1,373,6532, 32
25,326,0012, 3, 53
3,215,031,7512, 3, 5, 74
2,152,302,898,7472, 3, 5, 7, 115
3,474,749,660,3832, 3, 5, 7, 11, 136
341,550,071,728,3212, 3, 5, 7, 11, 13, 177
3,825,123,056,546,413,0512, 3, 5, 7, 11, 13, 17, 19, 239
318,665,857,834,031,151,167,4612, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 3712
3,317,044,064,679,887,385,961,9812, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 4113

Record gaps between consecutive primes up to 10,000,000

Found by sieving every number up to 10,000,000: each row is a gap wider than every gap before it, from one prime to the next.
GapFrom the primeTo the next prime
123
235
4711
62329
88997
14113127
18523541
20887907
221,1291,151
341,3271,361
369,5519,587
4415,68315,727
5219,60919,661
7231,39731,469
86155,921156,007
96360,653360,749
112370,261370,373
114492,113492,227
1181,349,5331,349,651
1321,357,2011,357,333
1482,010,7332,010,881
1544,652,3534,652,507

How to check whether a number is prime

  1. Type the number. Enter a whole number from 0 up to 3,317,044,064,679,887,385,961,980. Commas are fine (1,000,003). The answer appears as you type: 7,919 is prime for 7919, with the method used underneath.
  2. Read the verdict and the evidence. A prime shows the method that proved it. A composite shows its smallest prime factor: for 91 it reads 7 (91 = 7 × 13). For 1 and 0 the page explains why they are not prime.
  3. Look at the nearest primes. The previous and next prime come with their distance: 7,907 (12 below) and 7,927 (8 above) for 7919, and the list shows the primes around the number.
  4. Switch to a range. Choose primes in a range and type two ends, such as 1 and 100: 25 primes from 1 to 100, 8 twin prime pairs, listed in a table. The ends can be up to 1,000,000,000,000, and the range up to 10,000,000 numbers long.
  5. Count the primes up to N. Choose count primes up to N and type N (up to 10,000,000): for N = 1,000 the answer is 168 primes up to 1,000, and the page compares it with the estimate N ÷ ln N. Use copy results to keep the answer.

Frequently asked questions

How do I check if a number is prime?
Try to divide it by the primes up to its square root; if none divides it exactly, it is prime. For 7,919 the square root is just under 89, so testing the divisors up to 88 is enough, and none divides it. Quick shortcuts rule out most numbers: an even number above 2 is divisible by 2, a number whose digits add up to a multiple of 3 is divisible by 3, and a number ending in 0 or 5 is divisible by 5. This checker does the full test for you: trial division up to 1,000,000,000,000, and the Miller-Rabin test above that.
Is 1 a prime number?
No. A prime has exactly two different factors, 1 and itself, and 1 has only one. The reason is practical: if 1 were prime, 6 = 2 × 3 = 1 × 2 × 3 = 1 × 1 × 2 × 3 would have many factorizations, and “every number is a product of primes in exactly one way” would be false. This is why mathematicians put 1 in a class of its own, a unit, neither prime nor composite. The first prime is 2.
Is 2 the only even prime number?
Yes. Every even number is divisible by 2, so an even number larger than 2 has the factors 1, 2 and itself, which is too many for a prime. Of the 25 primes up to 100, only 2 is even. The checker says so for 2 (2 is prime) and for 4 shows 2 (4 = 2 × 2).
Is 0 a prime number? Can a negative number be prime?
No to both. 0 is divisible by every whole number, so it has infinitely many factors where a prime has two (0 is not prime). Primes are positive whole numbers greater than 1 by definition, so negative numbers and fractions are never prime in the ordinary sense; the checker asks for a whole number of 0 or more.
How many prime numbers are there from 1 to 100, and to 1,000?
25 primes from 1 to 100 and 168 primes from 1 to 1,000. Counting up to N gives the same: 25 primes up to 100, 168 primes up to 1,000. The first 100 primes table lists them in order; the 100th prime is 541. The primes thin out: 40.00% of the numbers up to 10 are prime, 25.00% up to 100, 16.80% up to 1,000 and 6.65% up to 10,000,000, where the count is 664,579.
How does the checker test large numbers, and is the answer a proof?
Up to 1,000,000,000,000 it divides by 2, 3 and then 6k ± 1 up to the square root, which takes at most a few hundred thousand steps. Above that it uses the Miller-Rabin test with a fixed list of bases, the first primes. Published results show that for every number below 3,317,044,064,679,887,385,961,981 the list leaves no composite undetected, so a pass is a proof and not a probability. For example, the checker decided 1,000,000,000,039 with 5 bases and 1,000,000,000,000,000,000,000,007 with 13. Smaller numbers need fewer bases, as the Miller-Rabin table above shows.
Why does the checker stop at 3.3 × 10^24?
Because 3,317,044,064,679,887,385,961,981 is where the published proof for the fixed list of bases ends. Above it a few Miller-Rabin rounds would only say “very probably prime”, which is a probability and not a fact, so the page gives no answer instead. The limit has 25 digits; the primes used in encryption are much larger, since a 1,024-bit number has 309 digits.
How do I find the next prime or the previous prime?
Test the numbers after (or before) your number one by one until a prime turns up; skipping the even numbers halves the work. After 7,919 the next prime is 7,927 and the one before it is 7,907. After 1,000 it is 1,009, and the checker also finds them above 1,000,000,000,000: the next prime after 1,000,000,000,039 is 1,000,000,000,061. Primes get rarer as numbers grow, but there is always another one; the record-gaps table shows how long the wait can be.
What are twin primes?
Twin primes are two primes that differ by 2, such as (3, 5), (5, 7), (11, 13) and (17, 19). There are 8 pairs up to 100, 35 up to 1,000 and 58,980 up to 10,000,000. Apart from (3, 5), the number between two twins is always a multiple of 6. Whether there are infinitely many twin prime pairs is an open question; the range tab lists them for any range.
What does π(N), the prime-counting function, mean?
π(N) is the number of primes up to N, nothing to do with the circle constant: π(100) = 25 and π(1,000) = 168. The prime number theorem says π(N) is close to N ÷ ln N for large N. The ratio of the two is 0.921 at 10, 1.161 at 1,000 and 1.071 at 10,000,000, drifting down toward 1. The checker counts exactly by sieve up to 10,000,000; the table above has the figures for powers of ten.
How are the primes in a range listed, and how many can I get?
By a sieve of Eratosthenes: write down every number in the range and cross out the multiples of each prime up to the square root of the upper end. What is left is prime. The page counts every prime in the range exactly and lists the first 10,000. The ends can be as high as 1,000,000,000,000, with up to 10,000,000 numbers between them: from 999,999,999,800 to 1,000,000,000,000, for example, there are 9 primes, the first of them 999,999,999,847 and the last 999,999,999,989.
Which numbers look prime but are not?
Odd numbers that 3 and 5 do not divide fool the eye. The first ones are 49, 77, 91, 119, 121, 133, 143 and 161: 91 is the classic, 91 = 7 × 13. A number such as 561 (561 = 3 × 187) is a Carmichael number: it passes the simple Fermat test for every base that shares no factor with it, which is why the checker uses the stronger Miller-Rabin test, not the Fermat one. The last digit helps only a little: a prime above 5 ends in 1, 3, 7 or 9, but not every such number is prime. Below 1,000 there are 40, 42, 46 and 38 primes ending in 1, 3, 7 and 9 respectively.
What are the longest gaps between primes?
Gaps get wider on average, and every so often a new record is set. The first gap of 100 or more is 112, between 370,261 and 370,373; the widest up to 10,000,000 is 154, after 4,652,353. The record-gaps table lists all 22 record gaps up to 10,000,000, found by the checker’s sieve. On average the gap near N is about ln N, so primes get sparser but never stop.
Why are prime numbers 6k − 1 or 6k + 1?
Every whole number leaves a remainder of 0 to 5 when divided by 6. Remainders 0, 2 and 4 make it even, and 3 makes it a multiple of 3, so a prime above 3 can only leave 1 or 5, which is the form 6k + 1 or 6k − 1. The reverse does not hold (25 and 35 have that form), but it cuts the trial divisions by two thirds. All 23 primes from 5 to 100 have it. That is why the checker tries only 2 of every 6 numbers as divisors.
What are prime numbers used for?
Public-key encryption such as RSA rests on the fact that multiplying two large primes is easy and splitting the product back is hard: a 1,024-bit prime has up to 309 digits, far beyond this page’s limit of 3.3 × 10^24. Primes are also used in hash tables, in random number generators and in error-correcting codes, and they are the building blocks of every whole number: each number above 1 is a product of primes in exactly one way, which is the reason 1 is not counted as one. To see that product for a number, use the prime factorization calculator.
How is the Miller-Rabin test different from checking the divisors?
Checking divisors is certain but slow: for a number of 25 digits it would mean going up to the square root, 1,000,000,000,000. Miller-Rabin writes n − 1 as 2^s × d and checks a short chain of powers modulo n for a handful of bases; a prime always passes, and a composite is caught by nearly every base. With a fixed list of bases it needs only 13 such checks for a number of 25 digits, and below 3.3 × 10^24 that list is a proof. When a composite is caught it also looks for a small factor: 147,573,952,589,676,412,927 is composite yet has no prime factor below 1,000,000, so the page shows the witness (base 3 fails the test) and not a factor.

How it works

A prime is a whole number greater than 1 whose only positive divisors are 1 and itself; 0 and 1 are not prime, and 2 is the only even prime. The checker decides in two ranges, both exact. For a number up to 1,000,000,000,000 it tries 2, 3 and then the numbers 6k − 1 and 6k + 1 up to the integer square root, in ordinary arithmetic, which is exact below 2^53; the first divisor found is the smallest prime factor. Above that, up to (not including) 3,317,044,064,679,887,385,961,981, it divides by the primes up to 41 and then runs the Miller-Rabin test in BigInt arithmetic: write n − 1 = 2^s × d with d odd; a base a passes if a^d ≡ 1 or a^(2^r × d) ≡ −1 (mod n) for some 0 ≤ r < s; a base that fails proves n composite. The bases are the first k primes, where k depends on the size of n: the thresholds in the Miller-Rabin table are the smallest composite numbers that pass for every one of the first k primes (Jaeschke 1993; Sorenson and Webster 2015; OEIS A014233), so below each threshold the test cannot be wrong. The unit tests compare every number up to one million with a sieve, check that each threshold itself is rejected, and compare the verdict, previous prime and next prime of dozens of larger numbers with an independent implementation. A composite that Miller-Rabin catches is searched for a prime factor below 1,000,000. The previous and next prime come from testing odd numbers downward and upward with the same function. Ranges and counts use a segmented sieve of Eratosthenes: all numbers from the start to the end are marked prime, then the multiples of every prime up to the square root of the end are crossed out, starting at the prime’s square or at its first multiple in the range. The ends can be up to 1,000,000,000,000 and the range up to 10,000,000 numbers; π(N) is counted up to 10,000,000. A twin prime pair is p and p + 2, both prime and both inside the range. The share that is prime is rounded to two decimals with integer arithmetic; the estimate N ÷ ln N and its ratio to π(N) are the only floating-point values, rounded to a whole number and to three decimals. At most 10,000 primes are listed and the twin-primes table shows at most 200 rows, but every count covers the whole range. The reference tables are computed when the page is built, with the same functions: the first 100 primes and the π table by the sieve, the record gaps by a sieve of every number up to 10,000,000, and the worked examples by the checker itself.

Sources

Guides

More: Algebra and number theoryAll math & numbersAll toolsHome & DIY calculators