How to optimize algorithm to be able to determine 10 digit long prime numbers in java

Question

I am currently new to java and programming in general, I'm working on an algorithm that determines the prime numbers in specific given ranges. Currently it works with six ranges which are numbers under 1 billion, when I tried to determine a 10 digit long number it failed. I am aware it needs to be changed to long since the digit is out of range but I am not sure how.

this is the part of the code where it determines if the umber is prime:

public ArrayList<Integer> getPrimes(int StartPos, int n) {
    ArrayList<Integer> primeList = new ArrayList<>();

    boolean[] primes = new boolean[n + 1];
    for (int i = StartPos; i < primes.length; i++) {
        primes[i] = true;
    }
    int num = 2;
    while (true) {
         for (int i = 2;; i++) {
              int m = num * i;
              if (m > n) {
                    break;
              } else {
                    primes[m] = false;
              }
         }
         boolean nextNum = false;
         for (int i = num + 1; i < n + 1; i++) {
              if (primes[i]) {
                    num = i;
                    nextNum = true;
                    break;
              }
         }
         if (!nextNum) {
              break;
         }
    }
    for (int i = 0; i < primes.length; i++) {
         if (primes[i]) {
            primeList.add(i);           
         }      
    }
    return primeList;  
}

I was checking online and found that perhaps I could do it with vectors but I have no experience with them and Also they are relatively slower than an Array.

You should find a different method other than sieve of eratosthenes. http://stackoverflow.com/questions/32035259/fastest-algorithm-to-find-if-a-biginteger-is-a-prime-number-or-not I'm not finding any answers to your question other than splitting up the calc into 2 methods, first being the sieve. — Nick Ziebert, Mar 28 '17 at 20:40
`I am aware [arithmetic] needs to be changed to long since the [10th] digit is out of range [for int]` worse yet, a sieve conventionally represents odd numbers, and 5E9 is larger than Java's maximum index value `Integer.MAX_VALUE` -> [segmented sieve](http://stackoverflow.com/questions/32390232/sieve-eratosthenes-greater-than-int/32391314#32391314). — greybeard, Mar 29 '17 at 03:50

Mikhail Antonov · Answer 1 · 2017-03-28T20:54:35.450

You might try BigInteger#isProbablePrime: https://www.tutorialspoint.com/java/math/biginteger_isprobableprime.htm

import java.math.BigInteger;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.LongStream;

// Java 8
public class FindPrimes {
    public static void main(String[] args) {
        System.out.println("1 - 100 primes: " + findPrimes(1L, 99L));
        System.out.println("some 10-digit primes: " + findPrimes(99_999_999_999L, 20000L));
    }

    private static List<Long> findPrimes(long start, long quant) {
        return LongStream.rangeClosed(start, start + quant).filter(v ->
                BigInteger.valueOf(v).isProbablePrime(1)).boxed().collect(Collectors.toList());
    }
}

score 2 · Answer 2 · answered Mar 29 '17 at 13:16

You say you are learning, so I will give you an outline in pseudocode, not the answer.

In general the method to find a prime in a range is:

repeat
  pick a number in the range
until (the number is prime)

You want a ten digit number. One way to generate a candidate while avoiding obvious non-primes is:

start with digit in [1..9]  // No leading zero.
repeat 8 times
  append a digit in [0..9]
endrepeat
append a digit in [1, 3, 7, 9]  // Final digits for large primes.

That will give you a ten digit possible prime.

Now you need to test to check it is prime.

There are tests like Miller-Rabin that you could try, but probably not if you are a real beginner. I would suggest setting up a Sieve of Eratosthenes covering numbers to to 10,000 which is the square root of your upper limit of 10,000,000,000. That will give you fast access to all the primes below the square root of your number. Set up the sieve once only at the start of your program. Make it a separate Class, and include a int nextPrime(int n) method which returns the next prime after the supplied parameter. Once that is in place, then you can write a trial division method to test your ten digit number:

boolean method isPrime(tenDigitNumber)
  testPrime <- 2
  limit <- square root of tenDigitNumber  // Only calculate this once.
  while (testPrime < limit)
    if (tenDigitNumber MOD testPrime == 0)
      return false  // Number is not prime.
    else
      testPrime <- sieve.nextPrime(testPrime)
    endif
  endwhile
  return true  // If we get here then the number is prime.
end isPrime

Because you have set up the sieve in advance, this should run reasonably quickly. If it is too slow, then it is time to look at coding Miller-Rabin or one of the other heavy-duty prime test methods.

As well as the Sieve of Eratosthenes class, another useful utility method is an iSqrt() method that returns an integer square root. My own version uses the Newton-Raphson method, though no doubt there are other possibilities.

I believe `sqrt(10 000 000) = 100 000`. Otherwise, this is just what I needed to get my sieve up to 10 digits! — Brian J, Feb 23 '18 at 01:46

How to optimize algorithm to be able to determine 10 digit long prime numbers in java

2 Answers2