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