Sieve of Eratosthenes implementation not checking certain numbers

Question

I am writing a program to find prime numbers using the good ol' Sieve of Eratosthenes algorithm (although with a twist). In order to halve the size of the byte-array needed, I don't represent any even numbers, and stick with the odd (calculating their position in the array by integer division by two).

I have one problem, however. My program doesn't seem to recognize 17 or 113 as prime numbers, although they are indeed prime numbers. Here is my code:

public class Eratosthes {

    byte[] checklist;
    int range;

    public EratosthesConcurrent(int range) {
        this.range = range/2;
        this.checklist = new byte[this.range];
        this.initAllChecked();
        this.findPrimesSeq();
        this.printPrimes();
    }

    private void initAllChecked(){
        for(int i = 1; i < checklist.length; i++){
            checklist[i] = 1;
        }
    }

    private void crossOut(int i){
        checklist[i/2] = 0;
    }

    private void findPrimesSeq(){
        int curr = 3;
        outer: while(curr < range*2){
            for(int i = curr*curr; i < range*2; i+=2*curr){
                if(i != curr && i%curr == 0){
                    if(i == 113){
                        System.out.println(curr);
                    }
                    crossOut(i);
                }
            }

            secondLoop: for(int i = curr; i < range*2; i++){
                if(checklist[i/2] == 1 && curr != i){
                    curr = i;
                    break secondLoop;
                } else if(i == range*2-1 || i == range*2-2){ //Should be changed, might miss the last prime
                    break outer;
                }
            }
        }
    }

    public void printPrimes(){
        for(int i = 1; i < range; i++){
            if(checklist[i] == 1){
                System.out.println("Prime found: " + ((i*2)+1));
            }
        }
    }
}

Adding the following to the crossOut method does not produce any output:

if(i == 17 || i == 113){
    System.out.println("Found one of the numbers");
}

And that's very strange to me, because the printout from the program excludes 17 and 113, and thus does not check any of their multiples. This leaves me with an array of bytes where all primes are checked... as well as any multiple of 17 or 113.

I'd be very happy if somebody could find the error in my program -- I've been debugging it for hours myself, with no result. Thanks in advance.

Answer 1

The problem appears to be that you're not checking for division by 2.

You're calling crossOut(16) at some point (specifically as a multiple of 4), which crosses out the corresponding value for 17. Similarly for 112 causing 113 to be crossed out.

Change:

if (i != curr && i % curr == 0) {

to:

if (i % 2 != 0 && i != curr && i % curr == 0) {

and both of those gets printed as prime.

Also, I'm a bit concerned with what exactly that loop is doing - I didn't look at the output in too much detail, although it actually appears to be all the primes, but I imagine you should looping over multiples of curr, the first being 2*curr (not curr*curr), the increment between being curr (not 2*curr), although I'm not saying what you've done is incorrect, as I need a bit more time to understand exactly how your code is solving this problem.

Answer 2

for(int i = curr*curr; i < range*2; i+=2*curr){

first value = 9 then goes to 15

curr = 3 - 3*3 = 9

i += 2 * curr = 9 + 6

pseudo:

outerNum = sqrt[range]
array[boolean] size of range
array[0 & 1] = false

for i = 2 to outernum
       for j  = i to range
           if j % i != 0
               array[j] = false

for i = array[boolean] length
     print if array[i] = true

Thats from memory so forgive if any errors.