Neighboring Primes

Next & Previous Prime Calculator

Find the prime numbers immediately before and after any number, see which prime is closest, and view step-by-step distances on a number line.

Quick Examples:
Prime Number Line
Previous (< n) 89
-1 ←
Your Number 90
+7 →
Next (> n) 97
Nearest Prime Number
89 (distance: 1)
Closest prime on the number line
Largest Prime ≤ Your Number
89
Largest prime up to 90
01

Slide to Explore Neighboring Primes

Slide across numbers 1 through 35 to watch how the previous prime, your number, and the next prime move across the number line:

n = 10
Prev Prime 7
← 3
Number 10
1 →
Next Prime 11
Nearest prime is 11 (distance: 1).
02

Exact Halfway Ties Between Primes

When a number lands exactly halfway between two neighbor primes, both primes are equally close. Click a famous tie case below to see both equidistant primes:

Middle Number (n): 6
Lower Prime: 5 (distance: 1)
Upper Prime: 7 (distance: 1)

Since 6 is 1 step from 5 and 1 step from 7, both 5 and 7 are equally close nearest primes.

03

Why There Is No Prime Before 2

Why does the calculator return “None” for previous primes when your number is 2 or less? Because prime numbers are defined as whole numbers greater than 1:

For n = 2

2 is the very first prime number. There are no positive primes smaller than 2, so Previous Prime = None.

For n = 1

1 has only one divisor (itself) and is not prime. Previous Prime = None; Next Prime = 2.

For n ≤ 0

Zero and negative numbers cannot be prime numbers by mathematical definition.

04

Bertrand's Rule: Why a Next Prime is Always Guaranteed

Can you ever get stuck in an endless stretch of numbers without finding another prime? In 1850, mathematician Pafnuty Chebyshev proved Bertrand's Postulate: between any whole number n (> 1) and its double (2n), there is ALWAYS at least one prime number:

For any number n > 1: a prime p is always guaranteed between n and 2n
Guaranteed Range (between n and 2n): (14, 28)
Primes inside this window: 17, 19, 23
05

Safe Prime Search: Finding Secret Pairs for Codes

In digital security systems, computers look for a safe prime q = 2p + 1 where both p and q are prime numbers. Click “Simulate Safe Prime Search” below to watch the computer test candidate numbers:

Ready
Click the button to simulate candidate tests...
06

Step-by-Step Search Trail: Watch the Search in Real Time

When looking for the next prime above or previous prime below your number, the computer checks each integer in order until it hits a prime. Use this step-by-step tool to see every candidate tested and why composites get ruled out:

Click “Trace Step-by-Step” to watch the search unfold.
07

Neighboring Primes Reference Table

The table below lists neighbor primes for key landmark numbers, small boundary cases, and ties. Click any row to automatically load that number into the calculator:

Number n Type Previous Prime Steps Back Next Prime Steps Ahead Nearest Prime Tie?
1 Neither None — 2 +1 2 No
2 Prime None — 3 +1 2 (distance 0) No
3 Prime 2 −1 5 +2 3 (distance 0) No
4 Composite 3 −1 5 +1 3 & 5 Yes (Tie)
6 Composite 5 −1 7 +1 5 & 7 Yes (Tie)
9 Composite 7 −2 11 +2 7 & 11 Yes (Tie)
10 Composite 7 −3 11 +1 11 No
15 Composite 13 −2 17 +2 13 & 17 Yes (Tie)
21 Composite 19 −2 23 +2 19 & 23 Yes (Tie)
26 Composite 23 −3 29 +3 23 & 29 Yes (Tie)
50 Composite 47 −3 53 +3 47 & 53 Yes (Tie)
90 Composite 89 −1 97 +7 89 No
97 Prime 89 −8 101 +4 97 (distance 0) No
100 Composite 97 −3 101 +1 101 No
1,000 Composite 997 −3 1,009 +9 997 No
08

How Neighboring Primes Work

Primes are scattered along the number line in uneven patterns. Here is how distance, gaps, and ties behave mathematically:

Distance on the Number Line

The distance to a prime is simply the difference between your number and that prime:

Distance = |Your Number − Prime|

If your number is already prime, the distance is 0. If it is composite, the nearest prime is whichever prime has the smallest distance (or both if there is a tie).

Prime Gaps & Twin Primes

The gap between two neighbor primes p and the next prime is simply how many steps lie between them:

  • Closest Possible Neighbors (Gap of 2): For odd numbers, the smallest possible gap is 2, creating twin primes like (3, 5), (5, 7), (11, 13), and (17, 19).
  • Widening Gaps: As numbers get into the millions and billions, the average gap between primes steadily widens, but primes never stop appearing.
  • Never Too Far: Bertrand's Postulate guarantees you will always find a prime before doubling your number.

Why Halfway Numbers Are Always Even

Whenever two odd primes have a gap greater than 2, their exact middle number is always composite:

Middle Number = (Lower Prime + Upper Prime) / 2

Adding two odd numbers always produces an even number. Dividing that even number by 2 gives a whole integer that is divisible by 2 (unless it is 2 itself). That is why ties always happen at composite numbers!

Modulo 6 wheel diagram showing candidate spokes 6k-1 and 6k+1 searched when finding next and previous primes
Stepping Along 6k ± 1 Spoke Lanes Neighboring prime search jumps immediately from one 6k ± 1 candidate to the next, bypassing all multiples of 2 and 3 automatically.
09

Step-by-Step Worked Walkthroughs

Here are four examples illustrating common cases you will encounter:

Example 1 • Composite Number

Find Neighbors for n = 90

  1. Check 90: Even number divisible by 2 → Composite.
  2. Search downwards: 89 has no divisors. 89 is prime! Distance = 90 − 89 = 1.
  3. Search upwards: 91 = 7 × 13; 92, 94, 96 even; 93, 95 composite; 97 is prime! Distance = 97 − 90 = 7.
  4. Result: Nearest prime is 89 (distance 1). Largest prime ≤ 90 is 89.
Example 2 • Prime Number Itself

Find Neighbors for n = 97

  1. Check 97: No divisors other than 1 and 97 → 97 is prime!
  2. Previous prime (< 97): 96 through 90 are composite; 89 is prime. Distance = 8.
  3. Next prime (> 97): 98 through 100 are composite; 101 is prime. Distance = 4.
  4. Result: Nearest prime is 97 (distance 0). Largest prime ≤ 97 is 97.
Example 3 • Halfway Tie

Find Neighbors for n = 15

  1. Check 15: 15 = 3 × 5 → Composite.
  2. Search downwards: 14 is even; 13 is prime. Distance = 15 − 13 = 2.
  3. Search upwards: 16 is even; 17 is prime. Distance = 17 − 15 = 2.
  4. Result: Because both distances are 2, it is a tie! Both 13 and 17 are equally close nearest primes.
Example 4 • Boundary Cases

Checking Numbers at n = 2 and n = 1

  1. Primes begin at 2: {2, 3, 5, 7, ...}.
  2. For n = 2: No prime strictly less than 2 exists → Previous Prime = None. Next prime is 3.
  3. For n = 1: 1 is not prime → Previous Prime = None; Next prime is 2.
  4. Inclusive search: Largest prime ≤ 2 is 2; Largest prime ≤ 1 is None.
10

Where Neighboring Primes Are Used in Everyday Tech

Finding neighbor primes is surprisingly important in computers and digital security:

RSA

Preventing Easy Password Cracks

In RSA security, if the two secret primes p and q are too close together, hackers can quickly crack the code using Fermat's method. Key generators make sure primes are far apart.

DH

Secret Key Exchange

When devices create shared secret keys over Wi-Fi, they pick a starter number and search for the next safe prime (where both p and 2p + 1 are prime).

DB

Database Bucket Sizing

When fast database tables (like Python dictionaries) run out of space, they resize to the next prime number to prevent data items from colliding.

11

How Computers Search for Neighboring Primes

Here is how common computer algorithms search for the nearest or next prime number:

Algorithm Test Speed Typical Steps Needed Best Used Up To How It Works
Simple Division Slowest Dozens of trial checks Up to 1 million Divides each number by smaller numbers to find factors
Wheel Step Search (6k ± 1) Fast Only checks potential primes Up to 100 trillion Skips multiples of 2 and 3 automatically
7-Base Miller-Rabin Check Lightning Fast 7 fast math tests 100% exact up to 18 quintillion Used by production math engines and browsers
Advanced Proof Algorithms Very Fast Fast steps Thousands of digits Used in research computer algebra software

Related Prime Discovery Tools

Frequently Asked Questions

What is the difference between the next prime and the nearest prime?

The next prime is the very next prime number larger than your number. The nearest prime is whichever prime number is physically closest on the number line. If your number is already prime, the nearest prime is the number itself (distance 0).

What happens when a number is exactly halfway between two primes?

When a number sits exactly in the middle between two primes (like 6, which is 1 step away from both 5 and 7, or 9, which is 2 steps away from 7 and 11), you get a tie! Both primes are equally close.

Why is there no previous prime for numbers 2 or less?

The prime numbers start at 2. Because primes must be whole numbers greater than 1, there are no prime numbers smaller than 2.

What does 'Largest Prime ≤ N' mean?

It means the largest prime number that is less than or equal to your number. If your number is already prime (like 97), the answer is 97. If your number is composite (like 90), it gives the nearest prime below it (89).

Does Bertrand's rule guarantee that a next prime always exists?

Yes! Bertrand's Postulate (proven in 1850) guarantees that for every number n greater than 1, there is always at least one prime number between n and its double (2n). This guarantees you will never run out of primes.

How do computers find the next prime quickly for huge numbers?

Computers use fast tests like the Miller-Rabin primality test. Instead of checking every divisor, the computer skips even numbers and tests candidate numbers one by one, usually confirming a prime in just a few microsecond checks.