Check if a Number Is Prime
Solve this ProblemEasy10 min
Topics
BasicsLoopsMath
Companies
TCSInfosysWipro
Given a non-negative integer
n, return whether it's a prime number — a number greater than 1 with no positive divisors other than 1 and itself.
Both solutions share the same n < 2 shortcut; they only differ in how far the trial divisionTrial DivisionTesting candidate divisors one at a time with the modulo operator — any exact division means the number isn't prime. search needs to go. Checking every candidate up to n − 1 is the direct reading of the definition. Checking only up to √nSquare Root BoundAny factor pair of n has one factor ≤ √n and one ≥ √n — so if no divisor exists up to √n, none exists at all. relies on a simple fact about factor pairs to rule out the same composite numbers in dramatically fewer steps, especially for large n.
Test Case 1:
Input:n = 7
Output:true
Explanation:7 has no divisors other than 1 and itself.
Test Case 2:
Input:n = 10
Output:false
Explanation:10 is divisible by 2 (and 5).
Test Case 3:
Input:n = 1
Output:false
Explanation:1 isn't considered prime by definition.
Constraints
- ◆
0 ≤ n ≤ 1000000
Try the Dry Run
Approach & Solutions
Trial Division up to n − 1Good
Numbers below 2 are never prime. Otherwise, try every candidate divisor from 2 up to n − 1 — if any of them divides n evenly, n isn't prime. If none do, n is prime.
Time
O(n)Space
O(1)Java
1class Solution {
2 public boolean isPrime(int n) {
3 if (n < 2) {
4 return false;
5 }
6 for (int i = 2; i < n; i++) {
7 if (n % i == 0) {
8 return false;
9 }
10 }
11 return true;
12 }
13}Trial Division up to √nOptimal
If n has a divisor larger than √n, it must also have a matching divisor smaller than √n (their product is n), so that smaller one would already have been caught. That means checking candidates only up to √n — via i * i <= n, which avoids a separate square-root call — is enough to find every possible divisor.
Time
O(√n)Space
O(1)Java
1class Solution {
2 public boolean isPrime(int n) {
3 if (n < 2) {
4 return false;
5 }
6 for (int i = 2; i * i <= n; i++) {
7 if (n % i == 0) {
8 return false;
9 }
10 }
11 return true;
12 }
13}