//1007 素数对猜想(20 分)
//让我们定义d_n=p_n+1 - p_n,其中p_i是第i个素数。显然有d_1=1,且对于n>1有d_n是偶数
//“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。其中'_'表示下标
//现给定任意正整数N(<10^5),请计算不超过N的满足猜想的素数对的个数。
//输入格式:
//输入在一行给出正整数N。
//输出格式:
//在一行中输出不超过N的满足猜想的素数对的个数。
//
//输入样例:
//20
//输出样例:
//4
C:
#include <stdio.h>
#include <math.h>
int main(int argc, const char * argv[])
{
int N;//正整数N
scanf("%d", &N);
int prime[100000] = {2,3};//2,3是素数但不是猜想素数对,为方便,进行这样初始化,事实上数组大小不需要这么大。
int paircnt = 0;//素数对个数,当前是2,3,素数对个数为0
int current = 1;//标记,当current==1时表示是素数,current==0时非素数
int primecnt = 2;//为了方便对素数数组的添加设定的索引
for (int i = 4; i <= N; i++) {//从4开始到N找其中的素数
current = 1;//每次循环标记初始化为1
// for (int j = 2; j <= sqrt(i); j++) {//从2开始,只要判断“2~根号i”间的素数不能被当前数整除,则为素数
for (int j = 0; prime[j] <= sqrt(i); j++) {
// if (i % j == 0) {//整除,非素数
if (i % prime[j] == 0) {
current = 0;//标记为0
break;//只要有一个j使i为非素数,就可以跳出循环了
}
}
if (current == 1) {//如果标记为1,即当前数为素数的话
prime[primecnt] = i;//放入素数数组
primecnt++;//数组索引+1
}
}
// for (int i = 0; i < primecnt; i++) { //这段注释用于验证上述程序是否正确
// printf("%d ",prime[i]);
// }
for (int i = 0; i < primecnt; i++) {
if(prime[i+1] - prime[i] == 2) paircnt++; //这里要注意后面减前面,因为数组是0开始的
}
printf("%d\n",paircnt);
return 0;
}
与之前1007相比,此方案只需要把当前数和之前的素数相余。这样循环次数可以减少很多。这是我在做1013时看OliverLew的思路才明白的。
网友评论