Algorithm: List all prime number using Sieve of Eratosthenes

Question

I have implemented Sieve of Eratosthenes for finding the list of prime number from 1 to n. My code is working fine for inputs from 1 to 10,000 but I am getting following for values >100,000:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -2146737495
        at SieveOfEratosthenes.main(SieveOfEratosthenes.java:53)

I am able to find the issue, which is in the for loop when I am doing i * i as it is going out of Integer range (Integer.MAX_VALUE), but I could not find the solution. Can someone suggest me what changes can be done also I appreciate if someone suggest me any improvement for efficiency in this implementation?

public class SieveOfEratosthenes {

    public static void main(String[] args) {

        Integer num = Integer.parseInt(args[0]);
        Node[] nodes = new Node[num + 1];

        for(int i = 1; i < nodes.length; i++) {

            Node n = new Node();
            n.setValue(i);
            n.setMarker(true);

            nodes[i] = n;
        }

        for(int i = 1; i < nodes.length; i++) {

            if(nodes[i].getMarker() && nodes[i].getValue() > 1) {
                System.out.println("Prime " + nodes[i].getValue());
            } else {
                continue;
            }

            for(int j = i * i; j < nodes.length
                                    && nodes[i].getMarker(); j = j + i) {
                nodes[j].setMarker(false);
            }
        }

        System.out.println(l.size());

    }
}

class Node {

    private int value;
    private boolean marker;

    public void setValue(int value) {
        this.value = value;
    }

    public int getValue() {
        return this.value;
    }

    public void setMarker(boolean marker) {
        this.marker = marker;
    }

    public boolean getMarker() {
        return this.marker;
    }

    public String toString() {
        return ("Value : " + marker + " value " + value);
    }
}

I have also tried `Math.abs(j) < nodes.length` and it showed some improvement but still the problem is same for other inputs — Vishrant, Mar 13 '17 at 02:04
@ScaryWombat I already tried this, and I learned that array can not be accessed using long value. its in Java docs — Vishrant, Mar 13 '17 at 02:12
http://stackoverflow.com/questions/30805300/accessing-an-array-element-if-using-long-datatype-in-java this will help you — Vishrant, Mar 13 '17 at 02:13
Array indexes in Java are int values, as far as I understand, so the maximum number of locations in an array is about 2 billion. — David Choweller, Mar 13 '17 at 02:15
Doesn't explain why it's not working for numbers greater than 10,000, though. — David Choweller, Mar 13 '17 at 02:16
@DavidChoweller as I mentioned that i * i is going beyond Integer.MAX_VALUE and as Java uses two's complement its using `-2146737495` value to find the index in array which is array out of bound, and its 100,000 not 10,000 two zeros ;) — Vishrant, Mar 13 '17 at 02:18
see http://introcs.cs.princeton.edu/java/14array/PrimeSieve.java.html — Scary Wombat, Mar 13 '17 at 02:19
@DavidChoweller we can add the condition that you mentioned `j > 0` but still the problem is same right? I will not get result for more than 100,000 — Vishrant, Mar 13 '17 at 02:20
@Vishrant I didn't make the suggestion about `j > 0`. The Sieve of Eratosthenes algorithm that I know should easily work for 100,000 numbers. First it crosses out all even numbers. Then it goes from 3 to the square root of n, adding by 2 every time, and for each of these it crosses out all multiples of that number. — David Choweller, Mar 13 '17 at 02:30

score 3 · Accepted Answer · answered Mar 13 '17 at 02:33

Essentially, the for(int j = i * i;... loop is to cross out all multiples of i. It makes sense only to cross out starting from i * i, since all lesser multiples are already crossed out by their lesser divisors.

There are at least two ways to go from here.

First, you can start crossing out from i * 2 instead of i * i. This will get rid of the overflow. On the bad side, the complexity of the sieve would grow from O(n log log n) to O(n log n) then.

Second, you can check whether i * i is already too much, and if it is, skip the loop completely. Recall that it is essentially skipped anyway for i greater than the square root of nodes.length if no overflow occurs. For example, just add an if (i * 1L * i < nodes.length) before the loop.

fxleyu · Answer 2 · 2017-03-13T02:38:55.113

    for(int i = 1; i < nodes.length; i++) {
        if(nodes[i].getMarker() && nodes[i].getValue() > 1) {
            System.out.println("Prime " + nodes[i].getValue());
        } else {
            continue;
        }

TO

int limit = 2 << 14;
for(int i = 1; i < nodes.length; i++) {
    if(nodes[i].getMarker() && nodes[i].getValue() > 1 && i <= 2 << 15) {
        System.out.println("Prime " + nodes[i].getValue());
        if (i > limit) {
            continue;
        }
    } else {
        continue;
    }

Algorithm: List all prime number using Sieve of Eratosthenes

2 Answers2