CareerCup

this is duplicate. please remove this question

if(n%prime==0)
return false;
if(prime>squareRoot)
break;

the previous code adds 9 to prime numbers small change

use sieve's algorithm, takes O(n) time

Providing Google employee referral. @securefer.com

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++;
    }
}

#include <iostream>



bool check(long	int x)
{
  for (int i = 2; i * i	<= x; ++i)
    if (x % i == 0) return false;
  return true;
}


int main()
{
  long int x = 10000000;
  int nc = 0;
  while (nc < 5)
    if (check(++x )) {
      std::cout	<< x <<	"\n";
      nc ++;
    }
  return 0;
}

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.