/* @(#)Primes.java   31 October 2005 */

public class Primes
{

    public static IntArrayList getPrimesUpTo(int n) {
        IntArrayList primes = new IntArrayList();
        
        if (n <= 1)
            return primes;
        
        primes.append(2);
        
        for (int k = 3; k <= n; k +=2)
            if (isOddPrime(k, primes))
                primes.append(k);
        
        return primes;
    }
    
    
    public static IntArrayList getPrimesList(int size) {
        IntArrayList primes = new IntArrayList();
        
        if (size <= 0)
            return primes;
        
        primes.append(2);
        
        int k = 3;
        
        while (primes.getLength() < size) {
            if (isOddPrime(k, primes))
                primes.append(k);
            
            k += 2;
        }
        
        return primes;
    }
    
    
    private static boolean isOddPrime(int k, IntArrayList primes) {
        IntArrayListIterator iterator = primes.newIterator();
        
        // skip 2 at head of the list
        iterator.advance();
        
        while(iterator.hasData()) {
            int p = iterator.getData();
            
            int q = k / p;
            
            if (q < p)
                break;
            
            int r = k - p * q;
            
            if (r == 0)
                return false;
        }
        
        return true;
    }
}