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

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

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.

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

"Most efficient". LOL. Good luck.

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

AKS algorithm for primality testing

Comment hidden because of low score. Click to expand.
0
of 0 votes

wikipedia->AKS_primality_test

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

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.

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.

Comment hidden because of low score. Click to expand.
0
of 0 votes

LOL.

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

Sieve of Eratosthenes

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.

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

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

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

}

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