11.1 Prime

Use Prime to Find Prime

public static ArrayList<Integer> Prime(int max){

    ArrayList<Integer> primeNumList=new ArrayList<Integer>();

    primeNumList.add(2);

    for (int i=3;i<max;i+=2){
        if(isPrime(i, primeNumList)==true){
            primeNumList.add(i);
        }
    }
    return primeNumList;
}
//This version is optimize
//for 997 == It will check== 3 5 7 11 13 17 19 23 29 31 37 
public static boolean isPrime(int n, ArrayList<Integer> primeNumList) {

           for (int primeNum: primeNumList) {

               if (primeNum>Math.sqrt(n)) {
                   System.out.println();
                   return true;
               }
               if (n % primeNum == 0) {
                   System.out.print( " \t\tfalse\n");
                   return false;
               }
           }
           return true;
    }

Sieve

//O (n* loglog N) + o (n)
public static ArrayList<Integer> sieve2(int N) {
    boolean[] isPrime = new boolean[N + 1];
    //Arrays.fill(isPrime, true);
    for (int i = 0; i <= N; i++) {
        isPrime[i] = true;
    }

    isPrime[0] = isPrime[1] = false;

    // mark non-primes <= N using Sieve of Eratosthenes
    //for (int i = 2; i <= N; i++) {
    for (int i = 2; i <= Math.sqrt(N); i++) {            
        // if i is prime, then mark multiples of i as nonprime
        // suffices to consider mutiples i, i+1, ..., N/i
        if (isPrime[i]) {
            for (int j = 2; i * j <= N; j++) {
                isPrime[i * j] = false;
            }
        }
    }

    ArrayList<Integer> res = new ArrayList<Integer>();
    // count primes
    int primes = 0;
    for (int i = 2; i <= N; i++) {
        if (isPrime[i]){
            primes++;
            res.add(i);
        }
    }
    return res;
}