Google Interview Question
Software Engineer / DevelopersCountry: 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