Adding primes to a certain arraylist

Question

I am implementing a program to solve this problem. In my algorithm I used the fact that if an odd number is not divisible by any smaller prime number then it is prime itself. So I made a loop to increment a certain number by two and check if it is divisible by the smaller prime numbers in an ArrayList. If not it will be added to that ArrayList.

The problem is when watching the variables, 25 , 35 , 45 ...etc are added to that list! Here's my code :

public class q6_1 {
    static int x = 0;

    static ArrayList<Integer> primes = new ArrayList<Integer>();

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        q6_1.primes.add(3);
        for (int i = 5; i < 100000; i += 2) {
            ListIterator<Integer> li = q6_1.primes.listIterator();
            if (i % (li.next()) == 0) {
            } else {
                q6_1.x++;
                Integer toBeAdded = new Integer(i);
                li.add(toBeAdded);
                if (q6_1.x == 10001) {
                    System.out.println(i);

                }

            }
        }

    }
}

Answer 1

You check only if the new number is divisible by the first number in the list. So you eliminate only numbers divisible by 3.

Use a nested loop to go through the list. You can stop when a prime is greater than the square root of the number to test.

Answer 2

Your approach would be somewhat inefficient. Also 2 is considered a prime number. Check out http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes. Also if you don't want to actual implement the Sieve itself take a look at BigInteger which contains nextProbablyPrime which in itself creates the Sieve (not sure if it is the algorithm I provided in the wiki or a different one) and comes up with prime numbers.