Amazon Interview Question Software Engineer / Developers
0of 0 votesWrite a program for prime numbers? improve the number of divisions that you are performing from all the numbers from 1 to that number to some less numbers. improve by seeing if you can decrease the loop from n to some lesser number.
Country: United States
Interview Type: Phone Interview
u can tweak it further by saying the composite number will be divisible by a prime<=sqrt(n).sth like blw to find 1st n primes
int primes[n]
boolean isPrime
primes[0]=2,primes[1]=3
i=5
while primes[n-1]!=0
isPrime=true
for k=1 to n-2
if primes[k]>sqrt(i)
break
else if i%primes[k]==0
isPrime=false
break
if(isPrime)
primes[k+1]=i
i+=2
Asked about optimization in no.of divisons.
Here the initial case is 1 to n, little bit improved is 1 to n/2 but we have to use from 2 to sqrt(n)
For a given range of number say 1 to n we can check for primeness in the following
ie isPrime(int n)
1. if number is 1 or if n % 2 == 0 (if a number is even )then return false
2. use the axiom that if n has divisor from 1<d < n then it has divisor 1< do < sqrt(n)
isPrime(int n )
{
if ( (n ==1) || (n %2 ) == 0 )
return false;
if(n ==2 )
return true;
for(int i=3; i<=(int)sqrt.(n) ; i++)
if(n %i ==0)
return false;
return true;
}
If a number is divisible by a number less than itself, it is divisible by a number less than or equal to (int)Math.sqrt(n). Can you see why?
- eugene.yarovoi on October 31, 2011 Edit | Flag Reply