Introduction

To compute the next prime after a given prime N, the basic strategy is to test larger candidate numbers until one is prime. For everyday programming tasks, the efficient version is to skip even numbers and test divisibility only up to the square root of each candidate.

The Core Observation

If N is a prime greater than 2, then N is odd. That means the next prime must also be odd, so there is no reason to test even candidates.

The second key observation is about primality testing. To decide whether a candidate x is prime, you do not need to try every divisor from 2 to x - 1. It is enough to check divisors up to sqrt(x).

Why? If x had a factor larger than its square root, the matching paired factor would have to be smaller than the square root. So one of them would already have been found.

A Straightforward Algorithm

The algorithm looks like this:

1. if N < 2, handle that as a special case
2. set the candidate to N + 1 if needed
3. if the candidate is even and greater than 2, move to the next odd number
4. test the candidate for primality
5. if it is not prime, add 2 and try again

This is simple and effective for moderately sized integers.

Python Implementation

1import math
2
3def is_prime(x):
4    if x < 2:
5        return False
6    if x == 2:
7        return True
8    if x % 2 == 0:
9        return False
10
11    limit = int(math.isqrt(x))
12    for d in range(3, limit + 1, 2):
13        if x % d == 0:
14            return False
15    return True
16
17def next_prime(n):
18    if n < 2:
19        return 2
20
21    candidate = n + 1
22    if candidate > 2 and candidate % 2 == 0:
23        candidate += 1
24
25    while not is_prime(candidate):
26        candidate += 2
27
28    return candidate
29
30print(next_prime(2))    # 3
31print(next_prime(11))   # 13
32print(next_prime(97))   # 101

The loop skips every even number after the first candidate, which cuts the search roughly in half immediately.

Why the Square-Root Check Matters

A naive primality test for 101 might try dividing by every integer from 2 to 100. The square-root optimization only checks up to 10, because sqrt(101) is slightly above 10.

That changes the cost of each primality check substantially:

• naive trial division: up to x - 2 checks
• optimized trial division: about sqrt(x) / 2 odd checks

For small and medium inputs, this is usually enough.

A C++ Version

1#include <cmath>
2#include <iostream>
3
4bool isPrime(long long x) {
5    if (x < 2) return false;
6    if (x == 2) return true;
7    if (x % 2 == 0) return false;
8
9    long long limit = static_cast<long long>(std::sqrt(x));
10    for (long long d = 3; d <= limit; d += 2) {
11        if (x % d == 0) return false;
12    }
13    return true;
14}
15
16long long nextPrime(long long n) {
17    if (n < 2) return 2;
18
19    long long candidate = n + 1;
20    if (candidate > 2 && candidate % 2 == 0) {
21        candidate++;
22    }
23
24    while (!isPrime(candidate)) {
25        candidate += 2;
26    }
27
28    return candidate;
29}
30
31int main() {
32    std::cout << nextPrime(97) << "\n";
33}

This is the same algorithm in a compiled language. It is still based on trial division, just written differently.

When You Need Faster Methods

For very large numbers, repeated square-root trial division becomes too slow. That is where more advanced algorithms help:

• Miller-Rabin for fast probabilistic primality testing
• segmented sieves for finding many primes in a range
• deterministic variants for bounded integer sizes

But if the task is simply “given one prime, find the next prime” for normal integer sizes, the trial-division approach is usually the right first answer.

Common Pitfalls

One mistake is forgetting the special case for 2. It is the only even prime, so generic odd-only logic often needs a small guard for it.

Another issue is checking divisibility all the way to n - 1. That is correct but unnecessarily slow. The square-root bound is the standard optimization.

A third mistake is incrementing by 1 after the first odd candidate instead of by 2. That wastes half the work on even numbers that cannot be prime.

Summary

• To find the next prime after N, test larger candidates until one is prime.
• Skip even candidates once you are above 2.
• Test divisibility only up to the square root of the candidate.
• Trial division is simple and practical for ordinary input sizes.
• For very large numbers, switch to faster primality-testing algorithms.