[PTA][B1007]素数对猜想
程序员文章站
2024-03-15 15:49:36
...
题目描述
让我们定义dn为:dn=pn+1−pn,其中pi是第i个素数。显然有d1=1,且对于n>1有dn是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。现给定任意正整数N(<105),请计算不超过N的满足猜想的素数对的个数。
输入格式: 输入在一行给出正整数N。
输出格式: 在一行中输出不超过N的满足猜想的素数对的个数。
输入样例:
20
输出样例:
4
解题思路
判断i, i+1, i+2是不是素数,如果i 和i + 2是而i + 1不是,res++。
注意点
1.在判断过程当中如果每一次都判断三个数是否为素数,会卡时间。应当用一个bool数组存储之前的判断结果。
2.判断是否是素数时,如果从2开始一直判断到n会卡时间。应当只判断到sqrt(n)即可,因为一个数的因数如果不相等,必然分布在其平方根两侧。
AC代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <math.h>
using namespace std;
int isPrime(int n)
{
int sqr = (int)sqrt(1.0*n);
for (int i = 2; i <= sqr; i++)
{
if (n%i == 0)
return 0;
}
return 1;
}
int main()
{
int front, res, N;
res = 0;
scanf("%d", &N);
int Prime[100010];
for (int i = 0; i < 100010; i++)
Prime[i] = 1;
for(int i = 2; i + 2 <= N; i++)
{
if (Prime[i] == 1)
{
if(isPrime(i) && isPrime(i + 2))
{
if (isPrime(i+1) == 0)
{
res++;
Prime[i + 1] = 0;
}
}
else if(isPrime(i + 2) == 0)
Prime[i + 2] = 0;
}
}
cout << res;
}
上一篇: 【PAT】B1007 素数对猜想
下一篇: 位1的个数