孪生素数问题
孪生素数问题
时间限制：3000 ms | 内存限制：65535 KB
难度：3
描述
写一个程序，找出给出素数范围内的所有孪生素数的组数。一般来说，孪生素数就是指两个素数距离为2，近的不能再近的相邻素数。有些童鞋一看到题就开始写程序，不仔细看题，咱们为了遏制一下读题不认真仔细的童鞋，规定，两个素数相邻为1的也成为孪生素数。
输入
第一行给出N(0<N<100)表示测试数据组数。
接下来组测试数据给出m，表示找出m之前的所有孪生素数。
(0<m<1000000)
输出
每组测试数据输出占一行，该行为m范围内所有孪生素数组数。
样例输入
1
14样例输出
4
[cpp]
/*********************************
* 日期：2013-3-14
* 作者：SJF0115
* 题号: 南阳理工 题目26: 孪生素数问题
* 来源：http://acm.nyist.net/JudgeOnline/problem.php?pid=26
* 结果：AC
* 来源：
* 总结：
**********************************/
#include<stdio.h>
#include<math.h>
int prime[1000001];
//素数表
int Primes(int n){
int i,j;
for(i = 1;i <= n;i++){
//偶数
if(i % 2 == 0){
prime[i] = 0;
}
//奇数
else{
prime[i] = 1;
}
}
//奇数的倍数肯定不是素数
for(i = 3;i <= sqrt(n);i+=2){
if(prime[i]){
for(j = i+i;j <= n;j += i){
prime[j] = 0;
}
}
}
return 0;
}
int main(){
int N,M,count,i;
while(scanf("%d",&N) != EOF){
while(N--){
count = 0;
scanf("%d",&M);
//求素书
Primes(M);
//求孪生素数
for(i = 2;i <= M-2;i++){
if(prime[i] && prime[i+2]){
count++;
//printf("%d %d\n",i,i+2);
}
}
//两个素数相邻为1的也成为孪生素数。这样的只有一种情况2,3
if(M >= 3){
count++;
}
printf("%d\n",count);
}
}
return 0;
}
/*********************************
* 日期：2013-3-14
* 作者：SJF0115
* 题号: 南阳理工 题目26: 孪生素数问题
* 来源：http://acm.nyist.net/JudgeOnline/problem.php?pid=26
* 结果：AC
* 来源：
* 总结：
**********************************/
#include<stdio.h>
#include<math.h>
int prime[1000001];
//素数表
int Primes(int n){
int i,j;
for(i = 1;i <= n;i++){
//偶数
if(i % 2 == 0){
prime[i] = 0;
}
//奇数
else{
prime[i] = 1;
}
}
//奇数的倍数肯定不是素数
for(i = 3;i <= sqrt(n);i+=2){
if(prime[i]){
for(j = i+i;j <= n;j += i){
prime[j] = 0;
}
}
}
return 0;
}
int main(){
int N,M,count,i;
while(scanf("%d",&N) != EOF){
while(N--){
count = 0;
scanf("%d",&M);
//求素书
Primes(M);
//求孪生素数
for(i = 2;i <= M-2;i++){
if(prime[i] && prime[i+2]){
count++;
//printf("%d %d\n",i,i+2);
}
}
//两个素数相邻为1的也成为孪生素数。这样的只有一种情况2,3
if(M >= 3){
count++;
}
printf("%d\n",count);
}
}
return 0;
}
注意：
接下来组测试数据给出m，表示找出m之前的所有孪生素数。
但实际上包括m这个数。
测试用例：
m = 7
孪生素数：
2,3
3,5
5,7
补充：软件开发 , C++ ,
