## Akamai Interview Question

**Country:**United States

check if the number is of the form 6*k+1 or 6*k-1, if yes then it is a prime number , exceptions are 2 and 3

This is not always correct. (Example: 35)

The process of 6k+/-1 gives possible false positives. Though this is good process to indicate which number is NOT a prime number.

possible modification can be, do a 6k+/-1, then do a trial division (divide number by all integers between 2 and sqrt(number)).

Per wiki, sieve of Eratosthenes is a fast method to find primes up to 10 million.

```
public static boolean isPrime(int n) {
if (n <= 1) {
return false;
}
for (int i = 2; i < Math.sqrt(n); i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
```

Thanks for answer in stackoverflow for below explanation:

If a number n is not a prime, it can be factored into two factors a and b:

n = a*b

If both a and b were greater than the square root of n, a*b would be greater

than n. So at least one of those factors must be less or equal to the square

root of n, and to check if n is prime, we only need to test for factors

less than or equal to the square root.

Hence if we search till sqrt of n, we are bound to find at least one factor

of n, which is enough to show that n is not prime.

```
public class PrimeNumber
{
public boolean checkPrime(int x)
{
if(x==1 || x==2)
{
return true;
}
else if(x%2==0)
{
return false;
}
else
{
double y = Math.sqrt(x);
double k = Math.ceil(y);
for(int j = 3; j<=k; j=j+2)
{
if(x%j == 0)
{
return false;
}
}
return true;
}
}
public static void main(String args[])
{
PrimeNumber pn = new PrimeNumber();
System.out.println("17: " + pn.checkPrime(17));
System.out.println("37: " + pn.checkPrime(37));
System.out.println("125: " + pn.checkPrime(125));
System.out.println("98: " + pn.checkPrime(98));
}
}
```

```
public class PrimeNumber
{
public boolean checkPrime(int x)
{
if(x==1 || x==2)
{
return true;
}
else if(x%2==0)
{
return false;
}
else
{
double y = Math.sqrt(x);
double k = Math.ceil(y);
for(int j = 3; j<=k; j=j+2)
{
if(x%j == 0)
{
return false;
}
}
return true;
}
}
public static void main(String args[])
{
PrimeNumber pn = new PrimeNumber();
System.out.println("17: " + pn.checkPrime(17));
System.out.println("37: " + pn.checkPrime(37));
System.out.println("125: " + pn.checkPrime(125));
System.out.println("98: " + pn.checkPrime(98));
}
}
```

public class TestPrime {

public static void main(String[] args) {

// TODO Auto-generated method stub

System.out.println(checkPrime(17));

}

public static boolean checkPrime(int number){

boolean flag = true;

for (int i = 2; i <=number/2; i++) {

if(number% i ==0){

flag = false;

break;

}

}

return flag;

}

}

Check number is divided by 2 to given number Quare Root. This is the minimum number of division to get prime number. In code, you will use square as below

- Rajesh Kumar July 25, 2014