在java中如何优化算法以确定10位长素数

Question

我目前是java和编程的新手，我正在研究一种算法，它可以确定特定给定范围内的质数。目前它工作在六个范围内，数字小于10亿，当我试图确定一个10位数长度的数字时，它失败了。我知道它需要更改为long，因为数字超出了范围，但我不确定如何更改。

这是代码中确定数字是否为质数的部分：

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;  
}

我在网上查看，发现也许我可以使用向量，但我没有使用它们的经验，而且它们比数组相对要慢。

Answer 1

你可以试试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());
    }
}

Answer 2

你说你正在学习，所以我将用伪代码给你一个提纲，而不是答案。

一般来说，在一个范围内查找质数的方法是：

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

你想要一个十位数字。在避免明显的非质数的情况下生成候选对象的一种方法是：

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.

这会给你一个十位数的可能素数。

现在你需要测试来检查它是质数。

有像Miller-Rabin这样的测试，你可以尝试一下，但如果你是真正的初学者，可能就不会了。我建议设置一个Eratosthenes筛子，覆盖数字到10,000，这是您的上限10,000,000,000的平方根。这将使您快速访问您的数字的平方根以下的所有质数。仅在程序开始时设置筛子一次。使其成为一个单独的类，并包含一个int nextPrime(int n)方法，该方法在所提供的参数之后返回下一个质数。一旦准备就绪，您就可以编写一个试除法来测试您的十位数：

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

因为您已经提前设置了筛子，所以它应该运行得相当快。如果它太慢，那么是时候考虑编码Miller-Rabin或其他重载主要测试方法之一了。

除了Eratosthenes类的筛子之外，另一个有用的实用方法是返回整数平方根的iSqrt()方法。我自己的版本使用了牛顿-拉夫森方法，尽管毫无疑问还有其他可能性。