## Amazon Interview Question

SDE-2s**Team:**Amazon Prime

**Country:**United States

**Interview Type:**In-Person

something like this might work better

basically prime numbers are numbers that are only divisible by themselves and 1

but cheating at it we can check for n

1 divisibility by numbers less than n/2

2 and only by other prime numbers less than n/2

```
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
System.out.print("Enter the limit : ");
int n = in.nextInt();
boolean flag;
List<Integer> arr = new ArrayList<>();
for (int cntr = 2; arr.size() < n; cntr++) {
flag = true;
if (!arr.isEmpty()) {
int index = 0;
for (int slct = arr.get(index++); slct <= cntr / 2; slct = arr.get(index++))
if (cntr % slct == 0) {
flag = false;
break;
}
}
if (flag) {
arr.add(cntr);
System.out.print("" + cntr + "\t");
}
}
}
```

I think it's worth mentioning to the interviewer that since prime numbers do not change, it's always a good idea to pre-calculate the prime numbers using algorithms like "sieve of eratosthenes" and just use them whenever required.

For example, to get first N prime numbers, just make a lookup into a pre-calculated list of prime numbers and get first N numbers from there.

Having said that if the requirement is to calculate first N prime numbers, here is a simple code to get that.

```
public class FirstNPrimeNumbers {
public static void main(String[] args) {
int n = 10;
firstNPrime(n);
}
private static void firstNPrime(int n) {
int x = 1;
int i = 3;
System.out.print(2 + " ");
while(x < n) {
boolean prime = true;
//Check if there exists any number that divides I. If yes, its not a prime
for(int j = 2; j < Math.sqrt(i); j++) {
if(i % j == 0) {
prime = false;
break;
}
}
if(prime) {
System.out.print(i + " ");
x++;
}
i++;
}
}
}
Output:
======
2 3 4 5 7 9 11 13 17 19
```

We know that prime numbers can be generated using (6*i - 1) and (6*i + 1) formula where i >= 1.

```
vector<int> getPrimes(int n)
{
if (n <= 0)
return {};
if (n == 1)
return {2};
if (n == 2)
return {2, 3};
vector<int> ans{2,3};
for (int i = 1; ans.size() < n; i++)
{
ans.push_back(6*i - 1);
if (ans.size() == n)
return ans;
ans.push_back(6*i + 1);
}
return ans;
}
```

}

I don't believe amazon asks this.

- adr July 22, 2018