## Google Interview Question

Software Engineer / Developers**Country:**United States

can't you just use recursion to find the first 5 primes from 2 to 100? I believe the time complexity is O(n^2) because the for loop is calling a recursive function which is n/1

```
public ArrayList<Integer> first5Primes(){
ArrayList<Integer> primes = new ArrayList<Integer>();
for(int i = 2; i < 101; i++){
if(primes.size() == 5){
break;
}
if(primeHelper(i,i-1)){
primes.add(i);
}
}
return primes;
}
public boolean primeHelper(int i, int j){
if(j == 1)
return true;
else if(i % j == 0)
return false;
else
return primeHelper(i, j-1);
}
```

public class Prime {

public static void main(String[] args) {

int startnumber=1000000000;

int count=0;

while(count!=5){

boolean val=checkPrime(startnumber);

if(val==true){

count++;

System.out.println(startnumber);

}

startnumber++;

}

}

public static boolean checkPrime(int number){

for(int i=2;i<number/2;i++){

if(number%i==0)

return false;

}

return true;

}

}

public class Prime {

public static void main(String[] args) {

int startnumber=1000000000;

int count=0;

while(count!=5){

boolean val=checkPrime(startnumber);

if(val==true){

count++;

System.out.println(startnumber);

}

startnumber++;

}

}

public static boolean checkPrime(int number){

for(int i=2;i<number/2;i++){

if(number%i==0)

return false;

}

return true;

}

}

```
#include<iostream>
using namespace std;
bool checkPrime(int number){
for(int i=2;i<number/2;i++){
if(number%i==0)
return false;
}
return true;
}
int main() {
int startnumber=1000000001;
int count=0;
while(count!=5){
bool val=checkPrime(startnumber);
if(val==true){
count++;
cout<<startnumber<<endl;
}
startnumber++;
}
}
```

Use the fact that if n is not prime, then n has at least one factor less or equal to the square root of n.

Keep a list of primes so you don't have to check if composite numbers factor n. Expand it as needed.

An implementation in Java:

```
List<Integer> firstFivePrimesWithTenDigits() {
List<Integer> knownPrimes = new ArrayList<Integer>();
knownPrimes.add(2);
knownPrimes.add(3);
List<Integer> bigPrimes = new ArrayList<Integer>();
for (int i = 1000000001; bigPrimes.size() < 5; i += 2) {
if (isPrime(i, knownPrimes)) {
bigPrimes.add(i);
}
}
return bigPrimes;
}
// Assumes "knownPrimes" is a list of the first k primes from some k >= 2
boolean isPrime(int n, List<Integer> knownPrimes) {
int squareRoot = (int) Math.sqrt(n);
while (knownPrimes.get(knownPrimes.size() - 1) < squareRoot) {
addNextPrime(knownPrimes);
}
for (int i = 0; i < knownPrimes.size(); ++i) {
int prime = knownPrimes.get(i);
if (prime >= squareRoot) {
break;
}
if (n % prime == 0) {
return false;
}
}
return true;
}
// Takes in a list of the first k primes for some k >= 2 and makes it a list of the first k+1 primes.
void addNextPrime(List<Integer> knownPrimes) {
for (int i = knownPrimes.get(knownPrimes.size() -1) + 2; true; i += 2) {
if (isPrime(i, knownPrimes)) {
knownPrimes.add(i);
return;
}
}
}
```

This is a simple approach. More sophisticated solutions can be found by looking up "primality test" online.

this is duplicate. please remove this question

- Phoenix July 23, 2014