CODEWITHSUNDEEP
java
Frank
Frank

Reputation: 37

Sieve of Eratosthenes malfunction

I am trying to create a Sieve of Eratosthenes in Java but the code I wrote seems to be flawed. I was wondering if anyone else can spot my mistake since I cannot. The output I get is simply [2], which means that my main loop doesn't work. I have only just started Java so I would appreciate it if you could give a detailed answer.

My code: 

public static int[] primes(int n)
{
    //Variable assignement
    double sqrt;
    List<Integer> primes= new ArrayList<Integer>();
    //Adds 2 to primes so i don't need to include the even numbers in my for loop.
    if(n>1)
    {
        primes.add(2);
    }
    //For loop that goes through the oneven numbers up to n
    for(int counter1=3;counter1<=n;counter1+=2)
    {
        sqrt=Math.floor(Math.sqrt(0.0+counter1));
        //for loop that tests if the first for loops number is prime
        for(int counter2=0;sqrt<=primes.get(counter2);counter2++)
        {
            if(counter1 % primes.get(counter2) != 0 && counter2 ==sqrt)
            {
                primes.add(counter1);
            }

            if(counter1 % primes.get(counter2)==0)
            {
                break;
            }
        }
    }
    return convertIntegers(primes);
}
//Converts the list to an array
public static int[] convertIntegers(List<Integer> integers)
{
    int[] ret = new int[integers.size()];
    for (int i=0; i < ret.length; i++)
    {
        ret[i] = integers.get(i).intValue();
    }
    return ret;
}

Upvotes: 2

Views: 188

Answers (2)

Thomas
Thomas

Reputation: 88727

I didn't throughly check your code but there might be a precision problem involved. Note that double might not represent integer values precisely thus counter2 ==sqrt might be false even if sqrt seems to be an integer.

To prevent this, try the following:

//this is not necessarily a square root anymore, btw :)
int sqrt = (int) Math.floor( Math.sqrt( (double)counter1 ) );
...
for( ... ) {
  ...
  if(... && counter2 ==sqrt ) {
    ...
  }
  ...
}

Edit:

A slightly more through analysis yields this:

Assume n = 5, thus the following steps would be executed in your code:

  1. counter1 = 3
  2. sqrt = 1 // floor(sqrt(2))
  3. counter2 = 0
  4. counter1 % primes.get(counter2) != 0 && counter2 ==sqrt is false since 3 % 2 = 1 BUT 0 != 1
  5. counter1 % primes.get(counter2)==0 is false since 3 % 2 = 1
  6. counter2 = 1 (next iteration)
  7. primes.get(counter2) throws an exception since primes.get(1) needs primes to have at least 2 elements.

What you might try is counter2 <=sqrt instead.

Upvotes: 2

mcfinnigan
mcfinnigan

Reputation: 11638

if(counter1 % primes.get(counter2)==0);{
    break;}
}

is unlikely to help matters. You have a semicolon before the opening brace - your break will always be executed.

Upvotes: 3

Related Questions