[compass]

The challenge is to weed out all the prime numbers without using any kind of division (%, /). My code doesn't weed out certain numbers, such as many multiples of 5, the number 49, etc, and I am not sure why. Here is my code.

My logic for the for loops was this: Starting with the upper numbers of the ArrayList, find every number that is a multiple of that number and remove it from the ArrayList. Every time you find a multiple, increase the variable multiply, so the program knows what the next multiple to look for.

// program doesn't work yet.
import java.util.ArrayList;
// import java.util.ListIterator;

public class Sieve2
{
    public static void main(String[] args)
    {
        int upperLimit = 55;
        ArrayList<Integer> primes = new ArrayList<Integer>();

        // fill the array
        for(int i = 0; i < upperLimit; i++)
            primes.add(i + 1);

        for(int mult = upperLimit/2; mult > 1; mult--)
        {
            int remove = mult, multiply = 2;
            for(int index = 1; index < primes.size(); index++)
            {
                if((remove * multiply) > upperLimit) break; // save some time

                if((remove * multiply) == primes.get(index))
                {
                    primes.remove(index);
                    multiply++;
                }
            }
        }

        // print the array
        for(Integer j : primes)
           System.out.print(j + " ");
    }
}

And this is the output:

1 2 3 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55

[jon.kiparsky]

That's an interesting implementation of Erathosthenes' Sieve. I think you might be making things more complicated than you need to by using a dynamic ArrayList. Consider an implementation that uses an array of booleans, call it primes. If primes[n] is true, then n has not yet been found to be composite. If it is false, it has been shown to be composite. Start your counter i at 2. If i is false, skip it. If not, then for j less than i * upperLimit, mark i * j as false.

At the end of this, it is easy to demonstrate that you have exhaustively struck off all of the composite numbers, so any number not shown to be composite must be prime.

Your current algorithm is a little tricky to debug, but I suspect that the problem you're having is caused by the complexity of your implementation. The way to debug it would be to step though it: put in some print statements that report the state of parameters you're interested in, and watch how your program develops in execution. You'll probably see the error happen if you look for it.

[pbl]

You should break after you remove(index) because your next iteration will skip the the one just after

As Jon mentioned, better to use an array of boolean or a BitSet

[compass]

Thank you both