c - 如何改进寻找孪生素数

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 本身是否是素数，而是测试 b - 2 和 b + 2 之一或两者。然后，如果其中任何一个绝对是素数，则声明 b 是孪生素数之一。

mpz_nextprime 可能会返回非素数，因为它使用的是概率算法。

@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 调用。