import java.util.*;


public class Prime

{
        // test if n is a prime
        public static boolean isPrime(int n) throws IllegalArgumentException
        {
                if (n < 2)
                        throw new IllegalArgumentException();

                List primes = new ArrayList();
                primes.add(new Integer(2));

                if (n == 2)
                        return true;

                // test if n is even
                if (n % 2 == 0)
                        return false;

                // generate all primes up to n and add to primes list
                for (int i = 3; i <= n; i++)
                {
                        // test if i is a prime
                        int prime = 2;
                        double sqrtI = Math.sqrt(i);
                        int j = 0;
                        while (prime <= sqrtI)
                        {
                                if (i % prime == 0) // i is not a prime
                                        break;
                                j++;
                                prime = ((Integer)(primes.get(j))).intValue();
                        }

                        if (prime > sqrtI || j >= primes.size()) // i is a prime
                        {
                                // test if n is prime
                                if (n == i)
                                        return true;
                                else if (n % i == 0)
                                        return false;
                                else
                                        primes.add(new Integer(i));
                        }
                }

                return false;
        }

        // test if n is composite
        public static boolean isComposite(int n) throws IllegalArgumentException
        {
                if (n < 2)
                        throw new IllegalArgumentException();

                return !isPrime(n);
        }

        // get the number of primes <= n
        public static int getPrimeCount(int n)
        {
                List primes = getPrimes(n);
                return primes.size();
        }

        // get a list of primes <= n
        public static List getPrimes(int n)
        {
                List primes = new ArrayList();

                if (n < 2)
                        return primes;

                primes.add(new Integer(2));

                if (n == 2)
                        return primes;

                // generate all primes up to n and add to primes list
                for (int i = 3; i <= n; i++)
                {
                        // test if i is a prime
                        int prime = 2;
                        double sqrtI = Math.sqrt(i);
                        int j = 0;
                        while (prime <= sqrtI)
                        {
                                if (i % prime == 0) // i is not a prime
                                        break;
                                j++;
                                prime = ((Integer)(primes.get(j))).intValue();
                        }

                        if (prime > sqrtI || j >= primes.size()) // i is a prime
                                primes.add(new Integer(i));
                }

                return primes;
        }

        // get the nth prime
        public static int getPrime(int n) throws IllegalArgumentException
        {
                if (n <= 0)
                        throw new IllegalArgumentException();

                if (n == 1)
                        return 2;

                List primes = new ArrayList();
                primes.add(new Integer(2));

                // generate all primes up to nth prime and add to primes list
                int i = 3;
                while (primes.size() < n)
                {
                        // test if i is a prime
                        int prime = 2;
                        double sqrtI = Math.sqrt(i);
                        int j = 0;
                        while (prime <= sqrtI)
                        {
                                if (i % prime == 0) // i is not a prime
                                        break;
                                j++;
                                prime = ((Integer)(primes.get(j))).intValue();
                        }

                        if (prime > sqrtI || j >= primes.size()) // i is a prime
                                primes.add(new Integer(i));
                        i++;
                }

                return ((Integer)(primes.get(primes.size()-1))).intValue();
        }

        public static void main(String[] args)
        {
                System.out.println/(getPrimes(1000));
                if (Prime.isPrime(1000000000))
                        System.out.println/("1000000000 is a prime.");
                else
                        System.out.println/("1000000000 is composite.");
                System.out.println/("There are "+Prime.getPrimeCount(10)+" primes <= 10");
                System.out.println/("There are "+Prime.getPrimeCount(100)+" primes <= 100");
                System.out.println/("There are "+Prime.getPrimeCount(1000)+" primes <= 1000");
                System.out.println/("The 10th prime is "+Prime.getPrime(10));
                System.out.println/("The 100th prime is "+Prime.getPrime(100));
                System.out.println/("The 1000th prime is "+Prime.getPrime(1000));
        }


}