Expedia Interview Question
Software Engineer / DevelopersSomething like this:
bool is_prime(int num){
if(num<=3)return true;
if(num%2==0)return false;
for(int i=9;i<num;i+=2)
if(num%i==0)return false;
return true;
}
bool is_prime(int num)
{
if(num<=3)return true;
if(num%2==0)return false;
for(int i=5; i <=num/2;i+=2)
{
if(num%i==0)return false;
}
return true;
}
it can be made more efficient:
bool is_prime(int num){
if(num<=3)return true;
if(num%2==0)return false;
for(int i=5; i < sqrt(n);i+=2) //beyond sqrt(n)
if(num%i==0)return false; //no num can
return true; //divide n
}
This code snippet is highly inefficient:
Dont call sqrt(n) in for loop, because is possible to store the value for sqrt(n) in the local variable and then compare it with i.
There is multi exit point in the function, so it is good practice to have sigle exit point in the funtion and that should be at the end of the program. The reason for this is that for bigger functions it is difficult to debug the multi exit function.
The code should be:
bool isPrime(int n)
{
bool flag = true;
int temp = sqrt(n);
if(n <= 3)
{
flag = false;
}
else if( n % 2 == 0)
{
flag = false;
}
else
{
for(int i = 5; i< temp; i+=2)
{
if(n % i) == 0)
{
flag = false;
break;
}
}
}
return flag;
}
But to find all smaller prime number less than sqrt(n) is in efficient.
Its time complexity will be:
O(sqrt(n)) + O(sqrt(n-1)) + ......
But yes u can build a program that can learn from experience, the more u use the program the more it becomes efficient, but this too is space inefficent.
I mean to say that u can build a program that can memorize all the prime factor less than n. Now suppose if the function is called for value less than n, then the function already have all the prime factor less than n, but if the function is called for greater than n, then it will first find all the remaining prime factor and memorize it for the further references.
int a=2038074743;
int n=1;
int low,high;
low = (6*n)-1;
high = (6*n)+1;
if(a<=3) cout<<"Prime"<<endl;
else
{
while(low<=a)
{
if((a-low) == 0)
{
cout<<"Prime"<<endl;
break;
}
if(high<=a)
{
if((a-high) == 0)
{
cout<<"Prime"<<endl;
break;
}
}
n++;
low = (6*n)-1;
high = (6*n)+1;
}
}
if(low>a)
cout<<"Not Prime"<<endl;
A slightly less brute-forced way would be to use Euclid's algorithm, and recognize that n is never divisible by m if m > sqrt(n):
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(a, a % b);
}
int isPrime(int n)
{
int sqrt_n = sqrt(n);
int i;
for (i = 2; i < sqrt_n; i++)
{
if (gcd(n, i) > 1)
return FALSE;
}
return TRUE;
}
I'm sure there are better ways to do it than that, too.
isnumberprime(int x)
- Trooper December 15, 2006for (int i = 0; i < x; i++)
for (int j = 0; j < x; j++)
if (i * j == x)
return false;
return true;