## 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