寻找最大素数小于n [英] Find a largest prime number less than n

查看:335
本文介绍了寻找最大素数小于n的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我怎样才能找到一个最大素数小于n,其中n≤10 18? 请帮我找到一个有效的算法。

How can I find a largest prime number which is less than n, where n ≤ 10¹⁸ ? Please help me find an Efficient Algorithm.

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;

I used this approach but this is not efficient to solve for n>10^10;

如何优化这..

编辑: 解决方案:每个Ĵ使用素性测试。

Solution: Use Primality test on each j.

米勒拉宾中的费尔马的测试

推荐答案

我不认为这个问题应该这么快就被解雇,因为效率的是不那么容易确定在此范围内的号码。首先,考虑到平均最间隙 LN(P),是有意义的工作的从给定的下来 (N)。例如, LN(10 ^ 18)〜41.44),所以你可能认为周围的 41 迭代的平均的工作下来(N)。例如,测试:(N),(N - 2),(N - 4),...

I don't think this question should be so quickly dismissed, as efficiency is not so easy to determine for numbers in this range. First of all, given the average prime gap is ln(p), it makes sense to work down from the given (n). i.e., ln(10^18) ~ 41.44), so you would expect around 41 iterations on average working down from (n). e.g., testing: (n), (n - 2), (n - 4), ...

鉴于此的平均值的差距,下一步就是决定是否要使用一个天真的测试 - 通过撇检查整除&LT; =地板(开方(N) )。随着 N'LT; =(10 ^ 18),你将需要测试的素数&LT; =(10 ^ 9)。有<一href="http://en.wikipedia.org/wiki/Prime-counting_function#Table_of_.CF.80.28x.29.2C_x_.2F_ln_x.2C_and_li.28x.29"相对=nofollow>〜5000万素数在这个范围内。如果您愿意为precompute,汇总这些值(所有这些都适合32位),你有64位值的合理的测试 N'LT = 10 ^ 18 。在这种情况下,是一个200MB素表中的一个可以接受的方法? 20年前,它可能不是。如今,这不是一个问题。

Given this average gap, the next step is to decide whether you wish to use a naive test - check for divisibility by primes <= floor(sqrt(n)). With n <= (10^18), you would need to test against primes <= (10^9). There are ~ 50 million primes in this range. If you are willing to precompute and tabulate these values (all of which fit in 32 bits), you have a reasonable test for 64-bit values n <= 10^18. In this case, is a 200MB prime table an acceptable approach? 20 years ago, it might not have been. Today, it's not an issue.

结合素表,筛分和/或波克林顿的测试可能会提高效率。另外,如果存储器被更多的限制,在米勒罗宾测试<的确定性变体/一>与碱: 2,325,9375,28178,450775,9780504,1795265022 (SPRP集)。大多数复合材料的SPRP-2测试立即失败。

Combining a prime table with sieving and/or Pocklington's test might improve efficiency. Alternatively, if memory is more constrained, a deterministic variant of the Miller-Rabin test with bases: 2, 325, 9375, 28178, 450775, 9780504, 1795265022 (SPRP set). Most composites fail immediately with an SPRP-2 test.

问题的关键是 - 你有一个决定算法的复杂性之间进行,无论是理论和在执行方面的困难,并与空间/时间权衡的平衡

The point is - you have a decision to make between algorithmic complexity, both theoretical and in terms of implementation difficulty, and a balance with space/time trade-offs.

这篇关于寻找最大素数小于n的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆