Using Sieve of Erastothene to find primes 2 to 1000

Question

I've been trying to find some help on how to use the Sieve of Erastothenes to print the primes from 2 to 1000 using an array. I looked up how the Sieve works but am having trouble figuring out how to code it.

import java.util.*;
public class PrimeArray {

public static boolean isPrime(int n){
    if(n<=1){
        return false;
    }
    for(int i = 2; i*i<n; i++){
        if(i%n==0)
            return false;
    }
    return true;
}

public static void main(String[] args) {
    int[] array = new int[1000];
        for(int j = 2; j<array.length; j++){
            if(isPrime(j))
                System.out.println(array[j]);

            }

        }



    }

This isn't the [Sieve of Eratosthenes](http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes). It's using [trial division](http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Trial_division). — Fred Larson, Nov 14 '14 at 20:28

score 0 · Answer 1 · answered Nov 14 '14 at 20:38

Here is a quick version of the Sieve Of Eratosthenes:

public BitSet sieve(long max){
    if(max < 3) return;

    BitSet isPrime = new Bitset((int)(max + 1 / 2))
    ArrayList<Long> primes = new ArrayList<long>();

    primes.add(2)
    isPrime.set(0, true)

    max = (long) Math.sqrt(max);

    for(int i = 3; i < max; i+= 2){
        boolean a = true;

        for(int j = 0; j < primes.size(); j++){
            if(i % primes.get(j) == 0){
                a = false;
                break;
            }
        }

        if(a){
            primes.add(i);
            isPrimes.set((i - 1) / 2, true);
        }

    }

    return isPrime;
}

This is not the sieve of Eratosthenes, it uses trial division. — Henry, Nov 14 '14 at 20:45

score 0 · Accepted Answer · answered Nov 14 '14 at 20:42

Your isPrime() function uses trial division, and has two bugs. One, test if n % i == 0 not i % n == 0 and two (i * i) <= n (not (i * i) < n). It works correctly if I use,

public static boolean isPrime(int n) {
    if (n <= 1) {
        return false;
    }
    for (int i = 2; (i * i) <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

Java arrays aren't dynamic data structures. To use the above to get 2 to the last prime below 1000 into an array, you could do

public static void main(String[] args) {
    int[] array = new int[168]; // the 168th prime is 997
    int pos = 0;
    for (int j = 2; pos < array.length; j++) {
        if (isPrime(j)) {
            array[pos++] = j;
        }
    }
    System.out.println(Arrays.toString(array));
}

Using Sieve of Erastothene to find primes 2 to 1000

2 Answers2