如何改进孪生素数的查找

Question

所以我在 C 语言上使用 GMP 库来查找高于某个值的孪生素数。虽然我相信我的策略会奏效，但问题是它需要花费大量时间（我知道你得到的越高越难找到素数。）有没有办法优化搜索？这是我拥有的代码片段：

    mpz_ui_pow_ui(a, base, exponent);
    mpz_nextprime(b, a); // b is the next prime number after a.
                         // c and d will be prime + 2 and
                         // prime - 2.

    /* Fortunate of fortunalities, mpz_nextprime gives the next
       prime greater than what one adds in! */
    /* We need to test if numbers are prime too. */
    while (al == false) {
        mpz_add_ui (c, b, 2);
        mpz_add_ui (d, b, -2);
        if ((mpz_probab_prime_p(c, 15) == 2) ||
            (mpz_probab_prime_p(d, 15) == 2)) { // Returns 2
                                                // if c/d are
                                                // definitely
                                                // prime.
            mpz_set(firstprime,b); 
            al == true;
            break;
        }
        {
            mpz_nextprime(b, b); // b is the next prime number
                                 // after a. c and d will be
                                 // prime + 2 and prime - 2.
        }
    }
    printf("first twin is: ");
    mpz_out_str(stdout, 10, firstprime);
    printf("\n");
    printf("second twin is: ");
    if (mpz_probab_prime_p(c, 15) == 2) {
        mpz_out_str(stdout, 10, c);
    } else {
        mpz_out_str(stdout, 10, d);
    }
    printf ("\n");

Answer 1

不需要测试b - 2是否可以是素数，因为b是下一个大于[=12的素数=]a。这应该可以将您的搜索时间减半。对于非常大的数字，可能仍然太长。

Answer 2

你的算法有点奇怪。您不测试 b 本身是否是质数，而是测试 b - 2 和 b + 2 中的一个或两个。然后，如果其中任何一个肯定是质数，则声明 b 是孪生质数之一。

mpz_nextprime 可能 return 不是素数，因为它使用的是概率算法。

@chqrlie 正确地指出 b - 2 已经被 mpz_nextprime 处理过。唯一的边缘情况是，如果第一次调用 mpz_nextprime 的结果与 a.

只有一两个距离

既然你愿意接受b可能只是一个素数，那么如果两个都可能是素数你应该会很高兴。所以：

/* a won't be prime */
mpz_ui_pow_ui(a, base, exponent);

if (exponent == 0) {
    mpz_nextprime(firstprime, a);
} else {
    /* Handle the edge case of a - 1 and a + 1 being twins */
    mpz_sub_ui(b, a, 2);
    mpz_nextprime(firstprime, b);
}

for (;;) {
    mpz_add_ui(c, firstprime, 2);
    if (mpz_probab_prime_p(c, 15) > 0) {
        break;
    }
    /* Optimize out an mpz_set call, thanks @chqrlie */
    mpz_nextprime(firstprime, c);
}

这会发现可能是孪生素数。如果您希望至少有一个绝对是素数，您可以实施自己的素数测试，或者为 firstprime.

添加一个 mpz_probab_prime_p 调用

如何改进孪生素数的查找

How to improve finding Twin Primes

c

primes

gmp