找到一个小于n的最大素数

-2

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

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并不有效;

如何优化这个..

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

Miller Rabin，Fermat's Test。

来源

2013-05-04 upendrajat

我们坚持认为人们在这里提出编程问题。做一些研究，提出一个算法，然后如果你的某个方面难倒了你，就回到这里。 – 2013-05-04 15:05:44

我在这方面做了很多研究...使用了复杂度为O（nlog（n））的算法，但现在想要更高效.. – upendrajat 2013-05-04 15:07:36

您可能已经发现了这一点，但仍然给出了一些参考：http：// stackoverflow .com/questions/6741947/algorithm-to-find-largest-prime-number-smaller-than-x – 2013-05-04 15:11:44

我不认为这个问题应该如此迅速地被驳回，因为效率不容易确定这个范围内的数字。首先，考虑到平均素数差距为ln(p)，从给定(n)开始工作下降是有意义的。即ln(10^18) ~ 41.44)，所以你可以期待41迭代平均从(n)降低。例如，测试：(n), (n - 2), (n - 4), ...

鉴于这种平均差距，下一步是决定你是否希望使用一个天真的测试 - 检查由素数整除<= floor(sqrt(n))。使用n <= (10^18)时，您需要针对素数<= (10^9)进行测试。在这个范围内有质数~ 50 million。如果您愿意预先计算并列出这些值（所有这些值均适用于32位），则您可以对64位值n <= 10^18进行合理的测试。在这种情况下，200MB主表是一种可接受的方法吗？ 20年前，它可能不是。今天，这不是一个问题。

将筛选和/或Pocklington's test结合使用可能会提高效率。或者，如果内存受到更多限制，则以Miller-Rabin test的确定性变体为基础：2, 325, 9375, 28178, 450775, 9780504, 1795265022(SPRP set)。大多数复合材料通过SPRP-2测试立即失败。

问题是 - 您有决定在算法复杂性，理论和实现难度两方面做出决定，以及在空间/时间上的平衡。

来源

2013-05-04 15:38:53

找到一个小于n的最大素数

回答

相关问题