Is this the best way I can find max prime numbers I can handle?

Question

I'm trying to find how many prime number I can have until the product of biggest two is over Long.MAX_VALUE.

It's taking more than half an hour (and GBs of RAM)

public class Main {
    public static void main(String[] args) {
        ArrayList <Long> primes= new ArrayList<Long>();
        primes.add(2L);
        long i=3L;
        // Looping from 3, to the limit
        while (primes.size()<2||(primes.get(primes.size()-1)*primes.get(primes.size()-2)<Long.MAX_VALUE)) {             
            boolean isPrime = true;
            long maxDiv =Math.round(Math.sqrt(i));
            int j=0;
                while(primes.get(j)<maxDiv && isPrime) {
                if (i % primes.get(j) == 0) {
                    isPrime = false;
                }
                j++;
            }        
            if (isPrime) {
                primes.add(i);
                System.out.println(i);
            }
            i=i+2;
        }
        System.out.println("max size is: "+primes.size());
    }
}

EDIT

I'm also interested in how many prime numbers I get before reaching this limit. So a top-down approach wouldn't do the job.

Anyway, I realized that I would be able to reach those two number in my application, I would have become rich as hell in the meantime :)

I agree, I see no reason for a negative vote, given that you did an honest effort and provided code. a negative vote should always be explained by a comment (I wonder why that's not forced by StackOverflow). Re your problem, I suggest you read about the Sieve of Erathostenes: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes — Roberto Attias, Dec 30 '16 at 09:36
Someone submitted a close vote for this question because "Questions asking us to recommend or find a book, tool, software library, tutorial or other off-site resource are off-topic for Stack Overflow". WTF? — samgak, Dec 30 '16 at 09:39
The problem is that I don't know which is the maximum value (is what I'm looking for, afterall). So I couldn't define a list of numbers on which I could apply the Sieve — Igino Boffa, Dec 30 '16 at 09:39
Not sure if your algorithm actually work to completion, Long.MAX_SIZE is over 9E18, there's over 2E17 primes under 1E19, which means you'll be running out of memory far long before it's complete. You can't even store them into regular DB, since you need millions of terrabyte harddrive just to store the values — Martheen, Dec 30 '16 at 09:39
On the other hand if you work [down](http://stackoverflow.com/a/16376021/529282), you can get by with only 200MB of prime table — Martheen, Dec 30 '16 at 09:41
Why don't you start from sqrt(Long.MAX_SIZE) and find the primes immediately above and below it? You'll have to use a different primality test however. — samgak, Dec 30 '16 at 09:41
@Martheen, I'm not trying to find all primes I can store in a long variable, but how many of them can be multiplied (in couples) giving a result under the Long limit. I think it is far below this limit. — Igino Boffa, Dec 30 '16 at 09:42
Oh, got it. Your algorithm never complete because the multiplication [wraparound](http://stackoverflow.com/questions/3001836/how-does-java-handle-integer-underflows-and-overflows-and-how-would-you-check-fo), use BigInteger — Martheen, Dec 30 '16 at 09:49
What are you trying to do? If you only need an approximation it is ~ n/logn. https://en.wikipedia.org/wiki/Prime_number_theorem — Fakrudeen, Dec 30 '16 at 09:55
@Martheen, would it be correct: `while (primes.size()<2||prod.compareTo(BigInteger.valueOf(Long.MAX_VALUE))==-1)` , where `prod=BigInteger.valueOf(primes.get(primes.size()-1)*primes.get(primes.size()-2));`? — Igino Boffa, Dec 30 '16 at 10:04
@Igino Hmm, probably but using BigInteger is expensive anyway. Probably just run the test when you're over the square root of Long.MAX_VALUE? — Martheen, Dec 31 '16 at 05:08

score 1 · Accepted Answer · answered Dec 30 '16 at 10:38

There should be a faster way to do this. Consider the following:

Use the sieve or Eratosthenes for the numbers between 2 and Sqrt(Long.MAX_VALUE)
Find the next prime number (next) after the last prime number (last) found by the sieve.
If next*last is already bigger than Long.MAX_VALUE you're done.
If not find the next primenumber after next (lets call it next2)
next*next2 is bigger than Long.MAX_VALUE

The sieve of Eratosthenes has a time complexity of O(n*log(log(n)).

You'll only have to "brute force" 2 prime numbers that are bigger than Sqrt(Long.MAX_VALUE). Added to the time needed to calculate the sieve, this should be drastically faster than your approach!

To the point that you have to count the prime numbers:

It's really easy to count the number of primes while calculating the sieve!

I'll give this a try when my will be over :) – Igino Boffa Dec 30 '16 at 10:42 — Igino Boffa, Dec 30 '16 at 10:42

Is this the best way I can find max prime numbers I can handle?

1 Answers1