1007 素數對猜想 (20分)
題目地址：https://pintia.cn/problem-sets/994805260223102976/problems/994805317546655744
輸入格式：
輸入在一行給出正整數N，
輸出格式：
在一行中輸出不超過N的滿足猜想的素數對的個數，
輸入樣例
20
輸出樣例
4
我的理解
找到所有的從1到N之間的素數，素數相減差值為2時，素數對個數加1，
- 注意1, 2，都是素數的特殊性，
- 判斷素數時，大于2的偶數都不是素數，可以跳過，
- 判斷大于2的數n是不是素數時，只需判斷能不能被3到根號n整除即可，數學的知識，目前我也不知道為什么，
代碼段
#include<iostream>
#include<math.h>
using namespace std;
int main() {
int number = 0;
cin >> number;
int prime[number];
int index = 0;
if (number < 3) {
cout << 0 << endl;
} else {
// 外層遍歷，從1到需要判斷的數
prime[index++] = 1;
prime[index++] = 2;
for (int i = 3; i <= number; i += 2) {
// 如果是除了2 之外的偶數，都不是素數
if (i > 2 && i % 2 == 0) {
continue;
}
bool flag = true;
// 需要判斷i是否為素數的方式，如果有從 3到 (<=)i 的平方根之間的數j，
// 可以被j整除，則i不是素數 ，
int upperLimit = sqrt(i);
for (int j = 3; j <= upperLimit; j++) {
// 滿足整除，不是素數
if (i % j == 0) {
flag = false;
break;
}
}
// 是素數，存盤到prime陣列中
if (flag) {
prime[index++] = i;
}
}
// 統計相差為2 的素數對
int primeCounter = 0;
for (int i = 1; i < index; i++) {
if (prime[i] - prime[i-1] == 2) {
primeCounter++;
}
}
cout << primeCounter << endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/110926.html
標籤：其他
上一篇：PAT乙級1006