Code Logo

Prime Number Check

Published at25 Jul 2026
Created by
Number Theory Easy 1 views
Like0

Determine whether a given non-negative integer n is a prime number. Return true if n is prime, false otherwise. A prime number is a positive integer greater than 1 that has no positive divisors other than 1 and itself.

For example, 7 is prime because its only divisors are 1 and 7. 8 is not prime because it is divisible by 2 and 4. 1 is not prime by definition. 2 is the smallest and only even prime number. 0 is not prime.

Prime numbers are the building blocks of number theory and have profound applications in cryptography (RSA encryption relies on the difficulty of factoring large composite numbers), hashing (prime table sizes reduce collisions), and random number generation. The ability to test primality efficiently is a fundamental skill.

The simplest primality test checks divisibility from 2 up to the square root of n. If any number divides n evenly, n is composite. If none do, n is prime. We only need to check up to sqrt(n) because if n has a divisor larger than sqrt(n), its complementary divisor must be smaller than sqrt(n). This optimization reduces the time complexity from O(n) to O(√n).

Edge cases include n = 0 and n = 1 (both return false), n = 2 (return true), and n being a perfect square like 9 (the check should catch the square root divisor). The solution should handle these correctly.

Example Input & Output

Example 1
Input
7
Output
true
Explanation

7 is prime

Example 2
Input
1
Output
false
Explanation

1 is not prime

Example 3
Input
17
Output
true
Explanation

17 is prime

Example 4
Input
4
Output
false
Explanation

4 = 2x2, not prime

Example 5
Input
2
Output
true
Explanation

2 is prime

Algorithm Flow

Recommendation Algorithm Flow for Prime Number Check

Solution Approach

Check divisibility from 2 up to the square root of n. If any divisor is found, n is not prime.

function solution(n) {
  if (n < 2) return false;
  for (var i = 2; i * i <= n; i++) {
    if (n % i === 0) return false;
  }
  return true;
}

First reject n < 2 since primes must be greater than 1. Then loop i from 2 while i * i <= n. If n % i === 0, n has a divisor and is composite — return false. If the loop completes without finding any divisor, n is prime — return true.

The condition i * i <= n is equivalent to i <= Math.sqrt(n) but avoids the overhead of a floating-point sqrt call. It also works correctly for perfect squares: for n = 9, the loop runs i = 2 (2*2=4 <= 9, 9%2=1), i = 3 (3*3=9 <= 9, 9%3=0 → return false).

Time complexity is O(√n). Space complexity is O(1).

Best Answers

java
class Solution {
    public boolean solution(int n) {
        if(n<2)return false;
        for(int i=2;i*i<=n;i++){if(n%i==0)return false;}
        return true;
    }
}