-1

如何找到小于 n 的最大素数，其中 n ≤ 10¹⁸ ？请帮我找到一个有效的算法。

for(j=n;j>=2;j--) {
  if(j%2 == 1) {
    double m = double(j);
    double a = (m-1)/6.0;
    double b = (m-5)/6.0;
    if( a-(int)a == 0 || b-(int)b == 0 ) {
      printf("%llu\n",j);
      break;
    }
  }
}

我使用了这种方法，但这对于解决 n>10^10 并不有效；

这个怎么优化。。

编辑： 解决方案：对每个 j 使用素性测试。

米勒拉宾，费马检验。

4

1 回答 1

7

我认为这个问题不应该这么快就被驳回，因为对于这个范围内的数字来说，效率并不是那么容易确定的。首先，考虑到平均质数差距 是，从给定的向下ln(p)工作是有意义的。即，因此您会期望从. 例如，测试：(n)ln(10^18) ~ 41.44)41(n)(n), (n - 2), (n - 4), ...

鉴于这个平均差距，下一步是决定您是否希望使用朴素测试 - 检查素数的可分性<= floor(sqrt(n))。使用n <= (10^18)，您将需要针对 primes 进行测试<= (10^9)。在这个范围内有大约 5000 万个素数。如果您愿意预先计算并将这些值制成表格（所有这些值都适合 32 位），那么您就可以对 64 位值进行合理的测试n <= 10^18。在这种情况下，一个 200MB 的素数表是可接受的方法吗？20年前，可能还不是。今天，这不是问题。

将素数表与筛分和/或波克林顿检验相结合可能会提高效率。或者，如果内存受到更多限制，则使用带有基数的Miller-Rabin 测试的确定性变体： 2, 325, 9375, 28178, 450775, 9780504, 1795265022 (SPRP set)。大多数复合材料通过 SPRP-2 测试立即失败。

关键是 - 你必须在算法复杂性（理论上和实现难度方面）与空间/时间权衡之间做出决定。

于 2013-05-04T15:38:53.890 回答