Determine whether an integer greater than 1 has no divisors other than 1 and itself.
Only test divisors up to sqrt(n): if n has a factor larger than its square root, it must also have a smaller one. Numbers <= 1 are not prime; 2 is the only even prime. Skipping evens after 2 halves the work. O(sqrt n).
public static boolean isPrime(int n) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 == 0) return false;
for (int i = 3; (long) i * i <= n; i += 2)
if (n % i == 0) return false;
return true;
}function isPrime(n) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 === 0) return false;
for (let i = 3; i * i <= n; i += 2)
if (n % i === 0) return false;
return true;
}def is_prime(n):
if n <= 1:
return False
if n <= 3:
return True
if n % 2 == 0:
return False
i = 3
while i * i <= n:
if n % i == 0:
return False
i += 2
return TrueThe sqrt(n) optimization is the classic "do you see the redundant work?" signal — the same instinct that flags an accidental O(n^2) loop.
Looping i from 2 to n-1 times out for large n. What single change helps most?