PTA 7-5 素数排位(10 分)

简介: PTA 7-5 素数排位(10 分)

已知素数序列为 2、3、5、7、11、13、17、19、23、29……,即素数的第一个是 2,第二个 是 3,第三个是 5……那么,随便挑一个数,若是素数,能确定是第几个素数吗?如果不是 素数,则输出 0。 输入格式: 测试数据有多组,处理到文件尾。每组测试输入一正整数 N(1≤N≤1000000)。 输出格式: 对于每组测试,输出占一行,如果输入的正整数是素数,则输出其排位,否则输出 0。

输入样例:

2

6

4

5

13

991703

输出样例:

1

0

0

3

6

77901

#include <stdio.h>
#include <math.h> 
int prime(int x)//求素数函数,素数返回 1,否则返回 0
{ int i; 
 for(i=2;i<=sqrt(x);i++)
 if (x%i==0) return(0);
 return(1);
}
int main(void)
{ int n,i,s;
while((scanf("%d",&n))!=EOF)
{ s=0;
if(prime(n)==0) 
 printf("%d\n",s);
 else
{ for (i=1;i<=n;i=i+2)
 if(prime(i)==1) s++;
 printf("%d\n",s);
}
}
return 0;
}

/*埃氏 Eratosthenes 筛选法(求一个范围中的所有素数) 我们用一个标记数组 f[maxi],其中 f[i]=0 为素数,否则为非素数,首先我们知道 1,和 0 都不是素数,所以 f[0]=1,f[1]=1 1.随后我们在未标记的数里面找最小的数,为 2,他不是任何数的的倍数,所以 2 是素数, 此时我们就把所有 2 的倍数都标记为 0;3,6,8,10……2*i 2.我们再从剩余未标记的数里面找最小的数,为 3,他也不是任何数的倍数,所以 3 是素数, 此时我们把所有 3 的倍数也都标记为 0;6,9,12,15,18……3*i 3.我们再从所有未标记的数里面找最小的数,为 5,他也不是任何数的素数,所以 5 是素数, 此时我们把所有 5 的倍数都标记为 0;10,15,20,25……5*i, …………以此类推 从 2 开始寻找素数,每次找到一个素数后就将它的倍数全部筛掉,不断循环,直至原队列 (数组)为空。 时间复杂度为 O(nlog logn)。*/

#include <stdio.h>
int main()
{ int n,len=0,i=0,k=0,a[1000]={0},b[1000]; // st[x]存储 x 是否被筛掉
while((scanf("%d",&n))!=EOF) { b[len++]=n;}
for (k=0;k<len;k++)
{
 if (b[k]==2) { a[k]=1;continue;}//偶数 2 是素数
 if (b[k]%2==0){ a[k]=0;continue;}//偶数肯定不是素数
 int st[1000000]={1,1,0};
 for(i=2;i<=b[k];i=i+1)
 {
 if(!st[i]) 
{ a[k]++;
 for(int j=2 * i; j<=b[k]; j=j+i)
 {st[j]=1;} 
}
 }
 }
for (k=0;k<len-1;k++)
{ 
 printf("%d\n",a[k]);
}
 printf("%d",a[k]);
return 0;
}
相关文章
【PTA】7-8 到底有多二 (15分)
【PTA】7-8 到底有多二 (15分)
2178 0
|
29天前
PTA-求100以内的素数
求100以内的素数
21 0
|
29天前
PTA-求指定范围内的素数
求指定范围内的素数
31 0
PTA 7-4 素数等差数列 (20 分)
2004 年,陶哲轩(Terence Tao)和本·格林(Ben Green)证明了:对于任意大的 n,均存在 n 项全由素数组成的等差数列。
80 0
PTA 7-4 最近的斐波那契数 (20 分)
斐波那契数列 F n ​ 的定义为:对 n≥0 有 F n+2 ​ =F n+1 ​ +F n ​ ,初始值为 F 0 ​ =0 和 F 1 ​ =1。
73 0
PTA 7-1 多二了一点 (15 分)
若一个正整数有 2n 个数位,后 n 个数位组成的数恰好比前 n 个数位组成的数多 2,则称这个数字“多二了一点”。
90 0
PTA 7-4 胖达与盆盆奶 (20 分)
俗称“胖达”,会排队吃盆盆奶。它们能和谐吃奶的前提,是它们认为盆盆奶的分配是“公平”的,即:更胖的胖达能吃到更多的奶,等胖的胖达得吃到一样多的奶。
116 0
PTA 1056 组合数的和 (15 分)
给定 N 个非 0 的个位数字,用其中任意 2 个数字都可以组合成 1 个 2 位的数字。要求所有可能组合出来的 2 位数字的和。
92 0
PTA 1017 A除以B (20 分)
本题要求计算 A/B,其中 A 是不超过 1000 位的正整数,B 是 1 位正整数。你需要输出商数 Q 和余数 R,使得 A=B×Q+R 成立。
71 0
PTA 1046 划拳 (15 分)
划拳是古老中国酒文化的一个有趣的组成部分。酒桌上两人划拳的方法为:每人口中喊出一个数字,同时用手比划出一个数字。
79 0

热门文章

最新文章