0

I'm trying to calculate all prime numbers of given a limit using the sieve of eratosthenes method. I know how to do that with big numbers as limit, but what if I try a real big number, larger than long type? I know I could use BigInteger but the problem is I don't know how to set a size of a boolean array(see the code) as BigInteger.

import java.util.ArrayList;
import java.util.Arrays;

public class Eratosthenes {

    private ArrayList<Integer> primes;
    private Integer limit;

    public Eratosthenes(Integer limit) {
        this.limit = limit;
        this.primes = new ArrayList<Integer>();
    }

    void sieve() {
        boolean[] allNumbers = new boolean[this.limit];

        Arrays.fill(allNumbers, Boolean.TRUE);

        for (int p = 2; (p * p) <= this.limit; p++)
            if (allNumbers[p] == true)
                for (int i = (p * 2); i < this.limit; i += p)
                    allNumbers[i] = false;

        for (int p = 2; p < this.limit; p++)
            if (allNumbers[p])
                this.primes.add(p);
    }

    void showResult() {
        System.out.println("[" + this.limit + "] primes: "  + this.primes.size());
    }

}


public class Main {
    public static void main(String[] args) {
        Eratosthenes eratostenes = new Eratosthenes(Integer.parseInt(args[0]));
        eratostenes.sieve();
        eratostenes.showResult();
    }
}
Roger_88
  • 477
  • 8
  • 19
  • The size of arrays and arraylists are limited by the max integer – OneCricketeer Oct 30 '19 at 02:21
  • 1
    You can fit more primes into a given array size by using one bit per number (`on` for prime, `off` for composite) and by only storing the bits for odd numbers since 2 is the only even prime. – rossum Oct 30 '19 at 09:20
  • As well you can use an array of arrays. To ease use, you define an `get(long)` method for retrieving and `set(long, boolean)` for setting a bit that abstracts away the indexing calculations. – President James K. Polk Oct 30 '19 at 18:02

0 Answers0