Define next prime precisely
The next prime after integer n is the smallest prime p such that p>n. Prime numbers are integers greater than 1 with exactly two positive divisors, 1 and themselves. The word “after” makes the comparison strict: if n is already prime, do not return n. For n<2, the next prime under this definition is 2.
Inputs: n=29. Formula: find minimum prime p with p>29. Calculation: test 30 composite, then 31; divisors need only be checked through √31, namely 2,3,5, and none divide. Result: 31. Interpretation: 29 is excluded even though prime. Verification: no integer lies between 29 and 31 except composite 30.
Generate sensible candidates
Start with n+1. Return 2 if the candidate is at most 2; otherwise move to the next odd integer and test odd candidates only. Every even integer greater than 2 is composite, so skipping evens halves candidate work without missing a prime. A 6k±1 filter can skip multiples of 2 and 3, but every surviving candidate still requires a primality test.
Inputs: n=100. Calculation: candidate 101 is odd; test divisibility by primes not exceeding √101≈10.05: 2,3,5,7. None divide. Result: 101. Interpretation: the first candidate is prime. Verification: 101 has no possible prime divisor at or below its square root.
Why testing through the square root is enough
If composite m=ab with integers 1<a≤b, then a≤√m. Therefore a composite candidate has at least one prime factor no larger than its square root. Testing divisibility beyond that limit repeats factor pairs. Check known primes as divisors, or test 2 then odd integers; stop when divisor²>candidate to avoid floating-point square-root boundaries.
Inputs: candidate 143. Formula: test possible prime divisors through √143≈11.95. Calculation: 143 is not divisible by 2,3,5, or 7, but 143/11=13. Result: composite. Interpretation: move to 145, then 147, 149; 149 passes tests through 12.2. Verification: next prime after 140 is 149 because 141–148 are composite.
A complete hand-worked search
Inputs: n=200. Candidate process: 201 is divisible by 3; 203=7×29; 205=5×41; 207 divisible by 3; 209=11×19; 211 has no divisor among 2,3,5,7,11,13 because √211≈14.53. Result: the next prime is 211.
Interpretation: checking only the final candidate is insufficient; “next” also requires showing that every intervening integer is composite. Verification certificates for composites can be short factor pairs, while the final prime is verified by trial division through its square root. This combination proves both primality and minimality.
Negative, decimal, and boundary inputs
The operation is defined on integers. A decimal input needs a stated rule, commonly find the smallest prime greater than the real number by starting above its floor; do not silently round to nearest. For any n<2, the next prime is 2. Extremely large inputs may exceed exact integer representation or practical search time in a browser.
Inputs: n=−12. Formula: minimum prime p>−12. Calculation: primes must be greater than 1, so 2 is the first eligible value. Result: 2. Interpretation: negative numbers, zero, and one are neither prime nor composite under the standard positive-integer classification. Verification: no prime smaller than 2 exists.
Algorithms for larger candidates
Trial division is transparent and suitable for modest integers. Software may accelerate by reusing a sieve for a range, dividing only by cached primes, or applying deterministic Miller–Rabin bases within a documented integer bound. A probable-prime test outside a proven range should not be described as an unconditional proof. Implementation claims must name the supported range and method.
Candidate addition can overflow a fixed-width integer near its maximum. Multiplication inside modular arithmetic can also overflow if not designed carefully. JavaScript Number represents all integers exactly only through 2⁵³−1; BigInt avoids that representation limit but does not make unlimited computation instant. NumUtility's checker documents its accepted range and rejects unsupported syntax rather than guessing.
Verification and practical limits
Audit the input as an integer, confirm strict greater-than behavior, list or factor intervening candidates, and independently test the result with divisors through its square root. For code, test boundaries n=−1,1,2,3, an even number, a prime input, a long composite run, and the maximum supported magnitude. Avoid treating a random search timeout as evidence that no prime exists.
Prime gaps vary, so there is no promise that the next prime is within a fixed small number of steps, although a next prime exists for every integer under standard mathematics. Cryptographic prime generation has additional requirements for randomness, bit length, validation, and side-channel resistance; a general educational next-prime routine is not a substitute for a reviewed cryptographic library.
Use the result in a reproducible workflow
A reproducible search records the starting integer, candidate rule, primality method, supported numeric range, and result. Inputs: n=1,000. Candidate sequence begins at 1,001. Calculation: 1,001=7×11×13; 1,003=17×59; 1,005 is divisible by 5; 1,007=19×53; 1,009 has no prime divisor at or below √1,009≈31.76. Result: 1,009.
Verification tests divisors 2,3,5,7,11,13,17,19,23,29,31 and finds none. Each skipped odd candidate has an explicit factor, establishing minimality. In a user interface, distinguish invalid input from a long-running search and never truncate a large integer silently. Returning an approximate scientific-notation value would make exact divisibility checks unreliable, so the tool should reject values beyond its documented exact range.
The previous prime and next prime are different operations. Around 1,000, the previous prime is 997 and the next is 1,009; neither distance is implied by the other. A nearest-prime tool would additionally need a tie rule, while a next-prime tool has no tie because it searches one direction. Naming the operation precisely prevents a correct prime from answering the wrong question.