一、題目:
題目鏈接
讓我們定義d?n??為：d?n??=p?n+1??−p?n??，其中p?i是第i個素數，顯然有d?i??=1，且對于n>1有d?n??是偶數，“素數對猜想”認為“存在無窮多對相鄰且差為2的素數”，
現給定任意正整數N(<105)，請計算不超過N的滿足猜想的素數對的個數，
二、輸入格式:
輸入在一行給出正整數N，
輸出格式：
在一行中輸出不超過N的滿足猜想的素數對的個數，
三、輸入樣例:
20
輸出樣例:
4
四、設計思路：
由于題目的要求是相鄰且相差為二的素數,所以我們可以直接令前面一個數為i，后面一個數就為i+2，
然后判斷這兩個數是否都是素數，如果是的話，那么統計素數對的變數就加1；外面再嵌套一個do-while
回圈就ok了，注意回圈的終止條件是i+2<=num,而不是i<=num,如果是i<=num的話，那么可能就會越界，
不滿足題目的要求，還有一點就是在素數的判斷的函式中，如果將判斷素數的回圈條件變為以下代碼：
for(i=2;i<num;i++)
if(num%i==0){ flag=0; break; }
雖然最后的結果不會出現問題，但是對程式的時間復雜度會有很大的影響，我在網上做這道題時最開始就是這么寫的，
由于那個網站的對程式運行的時間有限制，所以這樣寫就不能通過，需要改善代碼降低時間復雜度才能通過，于是
我就想對素數判斷的函式的回圈進行改進，本質上就是減少了回圈的次數，改進后的代碼如下：
for(i=2;i<=sqrt(num);i++) if(num%i==0){ flag=0; break; }
五、完整代碼:
#include<stdio.h> #include<math.h> int JudgePrimeNum(int num); int main() { int num; int i=1; int flag=0; scanf("%d",&num); do { if(JudgePrimeNum(i)==1&&JudgePrimeNum(i+2)==1) flag=flag+1; i++; } while (i+2<=num); printf("%d",flag); return 0; } //判斷數字是否為素數 int JudgePrimeNum(int num) { int flag=1; if(num==1){ flag=0; } else if(num==2||num==3){ flag=1; } else{ int i; for(i=2;i<=sqrt(num);i++) if(num%i==0){ flag=0; break; } } return flag; }
六、輸出效果：
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/49384.html
標籤：C
上一篇：列印沙漏
下一篇：log4j配置