Next Prime Number

Summary

Find the next prime number after a given number. A prime number is a natural number greater than 1 that has no divisors other than 1 and itself.

Detailed Explanation

To solve this problem, we can use a simple algorithm to check if a number is prime. We iterate from 2 up to the square root of the number, checking if it's divisible by any of these numbers. If it's not divisible by any of them, then it's a prime number.

Here's a step-by-step breakdown:

Start with the given number n.
Initialize a variable i to 2.
Loop until i is greater than the square root of n.
Inside the loop:
- Check if n is divisible by i. If it is, then n is not prime.
- If n is not divisible by i, increment i and continue to the next iteration.
Once the loop completes, return n + 1 as the next prime number.

Time complexity: O(sqrt(n)) Space complexity: O(1)

Optimized Solutions

Java

public class NextPrime { public static int nextPrime(int n) { if (isPrime(n)) { return n; } n++; while (!isPrime(n)) { n++; } return n; } private static boolean isPrime(int n) { if (n <= 1) { return false; } for (int i = 2; i * i <= n; i++) { if (n % i == 0) { return false; } } return true; } }