一、題目

讓我們定義d?n為：d?n=pn+1?pn，其中p?i是第i個素數。顯然有d1=1，且對于n>1有d?n是偶數。“素數對猜想”認為“存在無窮多對相鄰且差為2的素數”。 現給定任意正整數N(<10?^5)，請計算不超過N的滿足猜想的素數對的個數。輸入格式:輸入在一行給出正整數N。輸出格式:在一行中輸出不超過N的滿足猜想的素數對的個數。輸入樣例:20輸出樣例:4

二、代碼

方法一 ：

• 常用函數

本題目中需要自己掌握的就是素數的判斷！！！在代碼之后我詳細介紹了素數的相關知識！！

sqrt函數， 它不需要像在java中還需要Math.sqrt來調用，直接使用就行了。

• 核心思想
  1）本題最為核心的是不在于如何判斷素數，而在于素數判斷成功后如何保存，保存后再進行比較！
  所以我選擇了數組a[2]， 沒錯只有兩個元素，節省了很多空間。 它的存儲數值是動態的，只要有兩個數之后，不管滿足不滿足a[1] - a[0] == 2的條件，都要使a[0] = a[1], 讓a[1]來存儲新的素數!!!而且下標k也是動態變化的！！！！

• bug調試過程

開始時，我的問題是n與i不分， 因為是不超過n的數進行遍歷，所以這個i才是遍歷的對象， 我在后面isPrime的時候用的n
2）原文中是不超過n， 意思是包含n， 是i>=n
3）我原來將k下標的修改位置放在了if條件a[1] - a[0] == 2之下，發現是錯誤的； 因為滿足的只是少數，這樣a[2]一直得不到更新

#include <iostream> #include <math.h> using namespace std;bool isPrime(int n) {if(n <= 3) {return n > 1;}int m = (int)sqrt(n);for(int i=2; i <= m; i++) {if(n % i == 0) {return false;}}return true; }int main() {int n;cin>>n;int a[2];int k = 0, sum = 0;for(int i=1; i<=n; i++) {if(isPrime(i)) {a[k] = i;k++;if(k == 2) {if(a[1] - a[0] == 2) {sum++;}a[0] = a[1];k = 1;}}}cout<<sum;return 0; }

方法二：

在網上搜尋后，看到了另一種解決方法，感覺很簡潔，分享一下!!

• 核心思想

代碼將 N<=4 和 N >=3 做了分割，是我們需要警惕的！！可能因為n = 2， 3，5都是質數（素數），只要2和3兩個特殊！！

當n>3=時, 恢復正常判斷。只需要一個 **isPrime(i) && isPrime(i + 2)**就可以判斷出來， 讓我很佩服！！！！

#include <stdio.h> #include <math.h> #include <stdbool.h> bool isPrime(int);int main(void) {int N,i;int count = 0;scanf("%d", &N);if (N <= 4)printf("0");else{for (i = 3; i <= N - 2; i++)if (isPrime(i) && isPrime(i + 2))count++;printf("%d",count);} return 0; } bool isPrime(int n) {int i;if (n == 1 || n == 0)return false;else{for (i = 2; i <= sqrt((double)n); i++)if (n%i == 0)return false;}return true;

三、素數(轉載的)

作者：阿飛__
來源：CSDN
原文：https://blog.csdn.net/afei__/article/details/80638460
版權聲明：本文為博主原創文章，轉載請附上博文鏈接！

一、概念介紹

大家中學都學過，就不過多介紹了，大致提兩點：

• 質數又稱素數。一個大于1的自然數，除了1和它自身外，不能被其他自然數整除的數叫做質數；否則稱為合數。
• 0和1既不是質數也不是合數，最小的質數是2

Attention!!! 最小的質數是 2！！！！！ 所以當時1或者0的時候， 直接返回不是素數!!!

二、方法介紹

1.最直觀，但效率最低的寫法

public static boolean isPrime(int n){if (n <= 3) {return n > 1;}for(int i = 2; i < n; i++){if (n % i == 0) {return false;}}return true; }

這里特殊處理了一下小于等于3的數，因為小于等于3的自然數只有2和3是質數。
然后，我們只需要從2開始，一直到小于其自身，依次判斷能否被n整除即可，能夠整除則不是質數，否則是質數。

2.初步優化

假如n是合數，必然存在非1的兩個約數p1和p2，其中p1<=sqrt(n)，p2>=sqrt(n)。由此我們可以改進上述方法優化循環次數。如下：

public static boolean isPrime(int n) {if (n <= 3) {return n > 1;}int sqrt = (int)Math.sqrt(n);for (int i = 2; i <= sqrt; i++) {if(n % i == 0) {return false;}}return true; }

3.繼續優化

我們繼續分析，其實質數還有一個特點，就是它總是等于 6x-1 或者 6x+1，其中 x 是大于等于1的自然數。
如何論證這個結論呢，其實不難。首先 6x 肯定不是質數，因為它能被 6 整除；其次 6x+2 肯定也不是質數，因為它還能被2整除；依次類推，6x+3 肯定能被 3 整除；6x+4 肯定能被 2 整除。那么，就只有 6x+1 和 6x+5 (即等同于6x-1) 可能是質數了。所以循環的步長可以設為 6，然后每次只判斷 6 兩側的數即可。

public static boolean isPrime(int num) {if (num <= 3) {return num > 1;}// 不在6的倍數兩側的一定不是質數if (num % 6 != 1 && num % 6 != 5) {return false;}int sqrt = (int) Math.sqrt(num);for (int i = 5; i <= sqrt; i += 6) {if (num % i == 0 || num % (i + 2) == 0) {return false;}}return true; }

對于輸入的自然數 n 較小時，也許效果不怎么明顯，但是當 n 越來越大后，該方法的執行效率就會越來越明顯了。

總結

以上是生活随笔為你收集整理的PAT乙类1007之素数对猜想的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。