PROBLEM DESCRIPTION
Given a number N, verify if N is prime or not. Return 1 if N is prime, else return 0.
SOLUTION
If a is a factor of N, then N/a will also be its factor. So, we do not need to check for all numbers from 1 to N to check if it divides N. We can only go till sqrt(N). One thing to notice is that if N is a perfect square, there will be one a for which N/a is also same. For example: N=25. For a=5, b will also be same.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
public int isPrime(int A) {
int count = 0;
int sqrtA = (int)Math.ceil(Math.sqrt(A));
for(int i=1; i<=sqrtA; i++){
if(A%i == 0){
if(A/i == i) count++;
else count += 2;
}
if(count >= 3) return 0;
}
return count==2?1:0;
}
}