CODEWITHSUNDEEP
javanumberssumprimes
Moltehh
Moltehh

Reputation: 297

What's wrong with my Eratosthenes sieve

I was trying to find out the sum of all prime numbers below 2 million. Unluckily my Java Eratosthenes sieve doesn't seem to work properly. where is my error? Please don't post a completely different version of the code, just correct my error.

Here is my Java code:

public class Euler10 {

    public static void main(String args[])
    {
            int index;
            int k;
            int seq[]= new int[2000001];
            for (int i=0; i<seq.length; i++)
            {
                    seq[i] = i;
            }
            for (index=2; index<= (int) Math.sqrt(20000000); index++);
            {
                    if (seq[index]!=0)
                    {
                            k= index;
                            while (index<=(int) Math.sqrt(20000000))
                            {
                                    index *= k;
                                    seq[index]=0;
                            }
                    }
            }
            long somma =0;
            for (int siq:seq)
                    somma +=siq;
            System.out.println("somma "+somma);
    }
}

Upvotes: 1

Views: 129

Answers (2)

Prabhakaran Ramaswamy
Prabhakaran Ramaswamy

Reputation: 26094

for (index=2; index<= (int) Math.sqrt(20000000); index++);
                                                         |     
                                                         Remove this semicolon

Upvotes: 3

Jon Skeet
Jon Skeet

Reputation: 1499860

This is one problem:

index *= k;

Suppose k is 7. You want to remove 14, 21, 28 etc. Instead, you're removing 7*7, then 7*7*7, then 7*7*7*7 etc. You're also changing the value of index, which means you'll skip later numbers.

You want something like:

for (int multiple = 2; multiple * index < seq.length; multiple++) {
    seq[multiple * index] = 0;
}

EDIT: Ah - and Prabhakaran is correct about removing the ; after the declaration of the for loop too.

One point to learn from this is that you would have been able to spot both of these issues if you'd debugged through your code - or used another diagnostic technique such as adding significant amount of logging. It's very important to learn to be able to diagnose problems yourself. Before fixing the issue, I strongly suggest that you try to use a debugger to step through your existing broken code, and see where either the execution doesn't flow as you expect it to, or the values aren't what you expect them to be. That way you'll learn not just how to fix this error, but how to fix future ones too.

Upvotes: 2

Related Questions