package primenumber;

import java.util.ArrayList;
import java.util.List;

/**
 * To find prime number
 * @author Winston   Prakash
 */
public class PrimeNumber {
    
    /** Creates a new instance of PrimeNumber */
    public PrimeNumber() {
    }
    
    /*
     * Divide the number by all number below it starting from two.
     * If any of the reminder is zero then it is divisible and non prime
     */
    public List<Integer> bruteForce(int start, int end){
        List<Integer> primeNumbers = new ArrayList<Integer>();
        boolean isPrime;
        for(int i = start; i < end; i++){
            isPrime = true;
            for(int j = 2; j < i; j++){
                if ((i % j) == 0) {
                    isPrime = false;
                    break;
                }
            }
            if(isPrime) primeNumbers.add(i);
        }
        return primeNumbers;
    }
    
    /**
     * Find the next prime number
     */
    public int findNextPrime(int num){
        if ((num % 2) == 0){
            num++;
        }
        for (; !(isPrimeQuick(num)); num+= 2){
            ;
        }
        return num;
    }
    
    /*
     * Sieve of Eratosthenes algorithm
     * Eliminate all the numers which are multiples of current prime
     */
    public List<Integer> byElimination(int end){
        int[] primes = new int[end];
        List<Integer> primeNumbers = new ArrayList<Integer>();
        for (int i = 2; i < end; i++){
            if (primes[i] == -1){
                continue;
            }
            int mult = 2;
            int index = i * mult;
            while(index < end){
                primes[index] = -1;
                index = i * mult++;
            }
            primeNumbers.add(i);
        }
        return primeNumbers;
    }
    
    /*
     * Check if the numder is prime by dividing it by all its predecessor
     */
    public boolean isPrimeBruteForce(long number){
        boolean isPrime = true;
        for(long i = 2; i < number; i++){
            if ((number % i) == 0) {
                isPrime = false;
                break;
            }
        }
        return isPrime;
    }
    
    /*
     * Check if the numder is prime by dividing only by odd number
     * if it is not divisible by 2
     */
    public boolean isPrimeQuick(long number){
        boolean isPrime = true;
        if ((number % 2) == 0 ) return false;
        for(long i = 3; i < number/2; i += 2){
            if ((number % i) == 0) {
                isPrime = false;
                break;
            }
        }
        return isPrime;
    }
    
    public boolean isPrimeSuperQuick(long number){
        boolean isPrime = true;
        
        
        return isPrime;
    }
}