HTC Global Services Interview Question
Software DevelopersCountry: India
Interview Type: Written Test
I dig a little into Wikipedia, so my code takes advantage of the fact that every prime number can be described as 6k + 1 or 6k - 1, and the fact if you check if number is prime, you don't need to check bigger divisors than square root of number we check.
So isPrime(n) function checks if number can be divided by divisors that are smaller than sqrt(n) and can be described as 6k + 1 or 6k - 1 or 2 and 3. 2 and 3 are only valid divisors that are not 6k +-1.
countPimes(low, high) function check for primality only numbers that are between low and high, and can be described as 6k+1 or 6k-1.
public static boolean isPrime(int n)
{
if(n == 2 || n == 3)return true;
if(n % 2 == 0 || n % 3 == 0 || n <= 1)return false;
int i = 5;
int increment = 2;
while(i*i <= n)
{
if(n % i == 0)return false;
i+=increment;
increment=6-increment;
}
return true;
}
public static int countPrimes(int low, int high)
{
if(low > high)return -1;
//special cases because while loop checks numbers >= 5
if(low == high && low == 2 || low == high && low == 3)return 1;
int counter = (low <= 2 && high >=3) ? 2 : 0;
int increment;
//set first number to check if its prime checking only 6k-1 or 6k+1
if(low % 6 == 0){
low += 1;
increment = 4;
}else{
low = (((low/6) + 1)*6) - 1;
increment = 2;
}
while(low <= high)
{
if(isPrime(low))counter++;
//checking only numbers that can be described as 6k-1 or 6k+1. Increment provides this capability
low += increment;
increment = 6 - increment;
}
return counter;
}
public static void main(String []args){
System.out.println(countPrimes(32, 81));//11
}
- NoOne October 06, 2016