如何提高查找雙子彈

因此，我使用C語言的GMP庫來查找高於某個值的Twin素數。雖然我確信自己的策略能夠奏效，但問題變成了這樣一個事實，那就是花費大量時間（我知道在找到更高級別的素材時遇到困難。）有沒有一種方法可以優化搜索？下面是我的代碼的一個片段：如何提高查找雙子彈

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");

來源

2017-02-24 Marorin

還有其他一些檢查大質數的方法，比如Miller-Rabin素性檢驗，而沒有詳盡地找到所有較低質數。 –

當'mp'_probab_prime_p'爲'c'和'd'返回1時，您會忽略這種情況。 – jxh

mpz probab Miller-Rabin。 – Marorin

你的算法有點奇怪。您不測試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呼叫。

來源

2017-02-24 21:58:32 jxh

爲什麼（for;）的for循環？ – Marorin

我得到了休息時間，我的意思是for循環的條件 – Marorin

不需要進行條件檢查，因爲我們只對'break'感興趣。 'for（;;）'與'while（1）'相同。 – jxh

沒有必要測試是否b - ，2可以作爲總理b比一個下一個素數。這應該會縮短搜索時間。可能對於非常大的數字仍然太長。

來源

2017-02-24 21:42:13 chqrlie

基數爲2.指數爲64.下一個素數在2^64之後找到素數。 – Marorin

@Marorin：我站好了，回答更新了。 – chqrlie

如何提高查找雙子彈

回答

相關問題