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
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
- 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
- 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).
- 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.
- None of them divides 7,919 exactly, so 7,919 is prime.
- 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.
Primes in the range
The first 100 prime numbers
| Positions | Primes |
|---|---|
| 1st to 10th | 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 |
| 11th to 20th | 31, 37, 41, 43, 47, 53, 59, 61, 67, 71 |
| 21st to 30th | 73, 79, 83, 89, 97, 101, 103, 107, 109, 113 |
| 31st to 40th | 127, 131, 137, 139, 149, 151, 157, 163, 167, 173 |
| 41st to 50th | 179, 181, 191, 193, 197, 199, 211, 223, 227, 229 |
| 51st to 60th | 233, 239, 241, 251, 257, 263, 269, 271, 277, 281 |
| 61st to 70th | 283, 293, 307, 311, 313, 317, 331, 337, 347, 349 |
| 71st to 80th | 353, 359, 367, 373, 379, 383, 389, 397, 401, 409 |
| 81st to 90th | 419, 421, 431, 433, 439, 443, 449, 457, 461, 463 |
| 91st to 100th | 467, 479, 487, 491, 499, 503, 509, 521, 523, 541 |
How many primes there are up to 10, 100, 1,000 … 10,000,000
| x | π(x), the primes up to x | Share of 1 to x that is prime | x ÷ ln x | π(x) ÷ (x ÷ ln x) | Twin prime pairs up to x |
|---|---|---|---|---|---|
| 10 | 4 | 40.00% | 4 | 0.921 | 2 |
| 100 | 25 | 25.00% | 22 | 1.151 | 8 |
| 1,000 | 168 | 16.80% | 145 | 1.161 | 35 |
| 10,000 | 1,229 | 12.29% | 1,086 | 1.132 | 205 |
| 100,000 | 9,592 | 9.59% | 8,686 | 1.104 | 1,224 |
| 1,000,000 | 78,498 | 7.85% | 72,382 | 1.084 | 8,169 |
| 10,000,000 | 664,579 | 6.65% | 620,421 | 1.071 | 58,980 |
Primes in each block of 100 numbers, up to 1,000
| Numbers | Primes | Twin prime pairs | Widest gap | Share that is prime |
|---|---|---|---|---|
| 1 to 100 | 25 | 8 | 8 (89 to 97) | 25.00% |
| 101 to 200 | 21 | 7 | 14 (113 to 127) | 21.00% |
| 201 to 300 | 16 | 4 | 12 (211 to 223) | 16.00% |
| 301 to 400 | 16 | 2 | 14 (317 to 331) | 16.00% |
| 401 to 500 | 17 | 3 | 12 (467 to 479) | 17.00% |
| 501 to 600 | 14 | 2 | 18 (523 to 541) | 14.00% |
| 601 to 700 | 16 | 3 | 12 (619 to 631) | 16.00% |
| 701 to 800 | 14 | 0 | 14 (773 to 787) | 14.00% |
| 801 to 900 | 15 | 5 | 14 (839 to 853) | 15.00% |
| 901 to 1,000 | 14 | 0 | 14 (953 to 967) | 14.00% |
Worked examples: eight numbers, tested
| Number | Verdict | Method | Evidence | Previous and next prime |
|---|---|---|---|---|
| 1 | Neither prime nor composite | By definition | Only one factor | none and 2 |
| 91 | Composite | Trial division | Divisible by 7 | 89 and 97 |
| 561 | Composite | Trial division | Divisible by 3 | 557 and 563 |
| 7,919 | Prime | Trial division | No divisor up to 88 | 7,907 and 7,927 |
| 2,147,483,647 | Prime | Trial division | No divisor up to 46,340 | 2,147,483,629 and 2,147,483,659 |
| 1,000,000,000,039 | Prime | Miller-Rabin, 5 bases | All 5 bases pass | 999,999,999,989 and 1,000,000,000,061 |
| 147,573,952,589,676,412,927 | Composite | Miller-Rabin, 12 bases | Base 3 is a witness; no factor below 1,000,000 | 147,573,952,589,676,412,909 and 147,573,952,589,676,412,931 |
| 1,000,000,000,000,000,000,000,007 | Prime | Miller-Rabin, 13 bases | All 13 bases pass | 999,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
| Numbers below | Bases used | Number of bases |
|---|---|---|
| 2,047 | 2 | 1 |
| 1,373,653 | 2, 3 | 2 |
| 25,326,001 | 2, 3, 5 | 3 |
| 3,215,031,751 | 2, 3, 5, 7 | 4 |
| 2,152,302,898,747 | 2, 3, 5, 7, 11 | 5 |
| 3,474,749,660,383 | 2, 3, 5, 7, 11, 13 | 6 |
| 341,550,071,728,321 | 2, 3, 5, 7, 11, 13, 17 | 7 |
| 3,825,123,056,546,413,051 | 2, 3, 5, 7, 11, 13, 17, 19, 23 | 9 |
| 318,665,857,834,031,151,167,461 | 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 | 12 |
| 3,317,044,064,679,887,385,961,981 | 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41 | 13 |
Record gaps between consecutive primes up to 10,000,000
| Gap | From the prime | To the next prime |
|---|---|---|
| 1 | 2 | 3 |
| 2 | 3 | 5 |
| 4 | 7 | 11 |
| 6 | 23 | 29 |
| 8 | 89 | 97 |
| 14 | 113 | 127 |
| 18 | 523 | 541 |
| 20 | 887 | 907 |
| 22 | 1,129 | 1,151 |
| 34 | 1,327 | 1,361 |
| 36 | 9,551 | 9,587 |
| 44 | 15,683 | 15,727 |
| 52 | 19,609 | 19,661 |
| 72 | 31,397 | 31,469 |
| 86 | 155,921 | 156,007 |
| 96 | 360,653 | 360,749 |
| 112 | 370,261 | 370,373 |
| 114 | 492,113 | 492,227 |
| 118 | 1,349,533 | 1,349,651 |
| 132 | 1,357,201 | 1,357,333 |
| 148 | 2,010,733 | 2,010,881 |
| 154 | 4,652,353 | 4,652,507 |
How to check whether a number is prime
- 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.
- 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.
- 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.
- 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.
- 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
- Prime number, Wikipedia
- Primality test, Wikipedia
- Miller-Rabin primality test, Wikipedia
- Sieve of Eratosthenes, Wikipedia
- Twin prime, Wikipedia
- Prime-counting function, Wikipedia
- Prime gap, Wikipedia
- A014233: smallest odd number for which the Miller-Rabin test on the first n prime bases does not reveal compositeness, OEIS
- A000720: pi(n), the number of primes up to n, OEIS
- A001359: lesser of twin primes, OEIS
- Sorenson and Webster, Strong pseudoprimes to twelve prime bases, Mathematics of Computation (2017)
- Jaeschke, On strong pseudoprimes to several bases, Mathematics of Computation (1993)
Guides
- Prime Numbers and Fibonacci Numbers ExplainedWhat primes are, how trial division and the sieve of Eratosthenes find them, how Fibonacci numbers approach the golden ratio, and which ones are prime.
More free tools
- Factor CalculatorList every factor of a number with its factor pairs, count and sum, and whether it is prime, perfect or abundant. Plus common factors of 2 or 3 numbers.
- Factorial CalculatorCalculate n! exactly for any n up to 10,000: digit count, first and last digits, trailing zeros, n!!, subfactorial !n and Stirling’s approximation.
- Fibonacci CalculatorFind F(n) exactly for n up to 10,000, list the first N terms, test whether a number is Fibonacci, get its index, the sum of terms and the golden ratio.
- GCF and LCM CalculatorFind the GCF (GCD) and LCM of 2 to 20 numbers with Euclid’s algorithm, prime factors and multiples shown, plus Bézout coefficients and fraction reduction.
- Modulo CalculatorFind a mod n for any integers up to 200 digits, with floor and truncated remainders side by side, plus congruence, aᵇ mod n and the modular inverse.
- Complex Number CalculatorAdd, subtract, multiply and divide complex numbers exactly, then find the modulus, argument, polar form, powers, square roots and roots of unity.
More: Algebra and number theoryAll math & numbersAll toolsHome & DIY calculators