Akamai Interview Question


Country: United States




Comment hidden because of low score. Click to expand.
2
of 2 vote

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

static bool CheckPrime(int number)
        {
            for (int i = 2; i*i <= number; i++)
                if (number % i == 0)
                    return false;

            return true;
        }

- Rajesh Kumar July 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good approach.
need to add this comment:
if n is not prime, then n has at least one factor less or equal to the square root of n

- sp!de? July 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Miller–Rabin primality test
A primality test that provides an efficient probabilistic algorithm for determining if a given number is prime. It is based on the properties of strong pseudoprimes.

- Ajeet July 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

"Most efficient". LOL. Good luck.

- Anonymous July 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

AKS algorithm for primality testing

- Murali Mohan July 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

wikipedia->AKS_primality_test

- Murali Mohan July 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- nithin uppalapati July 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Rohitraman2006 July 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Rohitraman2006 July 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

LOL.

- Anonymous July 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sieve of Eratosthenes

- Milind Thombre July 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Algorithmy October 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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));
	}
}

- DJ May 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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));
	}
}

- DJ May 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

}

- Vipul Agarwal April 05, 2017 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More