Python Program to Find Next Prime Number

To find the next prime number in Python, use a function that checks if numbers greater than the input are prime by testing divisibility, like def next_prime(n): while True: n += 1; if is_prime(n): return n.

Examples

Input3

Output5

Input10

Output11

Input17

Output19

How to Think About It

To find the next prime number after a given number, start checking each number greater than the input one by one. For each number, test if it is divisible by any number from 2 up to its square root. If it is not divisible by any, it is prime. Return the first such number found.

Algorithm

1

Start from the number after the given input.

2

Check if the current number is prime by testing divisibility from 2 to its square root.

3

If it is prime, return this number as the next prime.

4

If not, move to the next number and repeat the check.

Code

python

def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(num ** 0.5) + 1):
        if num % i == 0:
            return False
    return True

def next_prime(n):
    candidate = n + 1
    while True:
        if is_prime(candidate):
            return candidate
        candidate += 1

print(next_prime(3))  # Output: 5

Output

5

Dry Run

Let's trace input 3 through the code to find the next prime number.

1

Start checking from 4

candidate = 4

2

Check if 4 is prime

4 % 2 == 0, so 4 is not prime

3

Move to next candidate 5

candidate = 5

4

Check if 5 is prime

5 is not divisible by 2, so 5 is prime

5

Return 5 as next prime

next_prime(3) returns 5

Candidate	Is Prime?
4	No
5	Yes

Why This Works

Step 1: Check divisibility to find primes

The code tests if a number is prime by checking if it has any divisor other than 1 and itself using num % i == 0.

Step 2: Start from next number

It begins checking from the number just after the input to find the next prime.

Step 3: Return first prime found

Once a prime number is found, the function returns it immediately as the next prime.

Alternative Approaches

Using a sieve to find primes

python

def next_prime_sieve(n):
    limit = n * 2  # simple limit
    sieve = [True] * (limit + 1)
    sieve[0], sieve[1] = False, False
    for i in range(2, int(limit ** 0.5) + 1):
        if sieve[i]:
            for j in range(i*i, limit + 1, i):
                sieve[j] = False
    for candidate in range(n+1, limit + 1):
        if sieve[candidate]:
            return candidate

print(next_prime_sieve(10))  # Output: 11

This method is faster for finding primes in a range but uses more memory and is less flexible for very large numbers.

Using sympy library's nextprime function

python

from sympy import nextprime
print(nextprime(10))  # Output: 11

Using a library is easiest and efficient but requires installing external packages.

Complexity: O(k * sqrt(m)) time, O(1) space

Time Complexity

For each candidate number k after input n, the code checks divisibility up to sqrt(m), where m is the candidate. This leads to O(k * sqrt(m)) time.

Space Complexity

The code uses only a few variables and no extra data structures, so space is O(1).

Which Approach is Fastest?

The sieve method is faster for ranges but uses more memory. The direct check is simple and uses less memory. Using a library like sympy is fastest and easiest if available.

Approach	Time	Space	Best For
Direct divisibility check	O(k * sqrt(m))	O(1)	Simple, small inputs
Sieve of Eratosthenes	O(n log log n)	O(n)	Finding many primes in a range
sympy nextprime	Optimized C code	Depends on library	Quick, reliable with external library