Amazon Interview Question Software Engineer / Developers
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;
}
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class PrimeTest2 {
/**
* @param args
*/
public static void main(String[] args) {
int count=0, p, numberOfPrimes;
List<Integer> primeList = new LinkedList<Integer>();
System.out.print("Enter the number of primes you want to get: ");
Scanner scan = new Scanner(System.in);
while(true){
if(!scan.hasNextInt()){
System.out.print("please enter only integer: ");
scan.next();
continue;
}else{
numberOfPrimes = scan.nextInt();
break;
}
}
p=1;
while(count<numberOfPrimes){
if(checkPrime(p)){
primeList.add(p);
count++;
}
p++;
}
System.out.println("First "+numberOfPrimes+" primes: "+primeList);
}
public static boolean checkPrime(int x){
int a, k;
if(x==1 || x ==2) return true;
if(x%2==0) return false;
k=3;
a=x/k+x%k;
while(k<=a){
if(x%k==0){
return false;
}else{
k+=2;
a = x/k+x%k;
}
}
return true;
}
}
{import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class PrimeTest2 {
/**
* @param args
*/
public static void main(String[] args) {
int count=0, p, numberOfPrimes;
List<Integer> primeList = new LinkedList<Integer>();
System.out.print("Enter the number of primes you want to get: ");
Scanner scan = new Scanner(System.in);
while(true){
if(!scan.hasNextInt()){
System.out.print("please enter only integer: ");
scan.next();
continue;
}else{
numberOfPrimes = scan.nextInt();
break;
}
}
p=1;
while(count<numberOfPrimes){
if(checkPrime(p)){
primeList.add(p);
count++;
}
p++;
}
System.out.println("First "+numberOfPrimes+" primes: "+primeList);
}
public static boolean checkPrime(int x){
int a, k;
if(x==1 || x ==2) return true;
if(x%2==0) return false;
k=3;
a=x/k+x%k;
while(k<=a){
if(x%k==0){
return false;
}else{
k+=2;
a = x/k+x%k;
}
}
return true;
}
}
}
The code below will give us the minimum number of divisions performed to check whether a number is prime or not.
public boolean checkPrime(int x){
if(x==1 || x==2) return true;
if(x%2==0){
return false;
}
int k = 3;
int a = x/k ;
while(k <= a){
if(x%k == 0){
return false;
}else{
k+=2;
a = x/k ;
}
}
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 October 31, 2011