找到小于n的最大素数

Question

如何找到小于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使用Primality测试.

米勒拉宾,费马的测试.

Answer 1

我不认为这个问题应该如此迅速地被驳回,因为在这个范围内的数字效率并不那么容易确定.首先,考虑到平均素数差距ln(p),从给定的下降是有意义的(n).也就是说,ln(10^18) ~ 41.44)所以你会期望平均41迭代次数从而减少.例如,测试:(n)(n), (n - 2), (n - 4), ...

鉴于这种平均差距,下一步是决定是否要使用天真测试 - 检查素数的可分性<= floor(sqrt(n)).有了n <= (10^18),你需要测试质数<= (10^9).在这个范围内有大约5000万个素数.如果您愿意预先计算这些值(并且所有这些值都适合32位),那么您可以对64位值进行合理的测试n <= 10^18.在这种情况下,200MB素数表是否可以接受？20年前,它可能不会.今天,这不是问题.

将主表与筛分和/或Pocklington测试相结合可以提高效率.或者,如果记忆更受限制,则使用碱基的Miller-Rabin检验的确定性变体:2, 325, 9375, 28178, 450775, 9780504, 1795265022 (SPRP组).大多数复合材料在SPRP-2测试中立即失效.

关键在于 - 您决定在算法复杂性之间做出理论和实施难度,以及与空间/时间权衡的平衡.