Posts Verify Prime (InterviewBit)
Post
Cancel

Verify Prime (InterviewBit)

PROBLEM DESCRIPTION

Given a number N, verify if N is prime or not. Return 1 if N is prime, else return 0.

InterviewBit

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;

    }
}
This post is licensed under CC BY 4.0 by the author.