当前位置: 代码迷 >> 综合 >> PAT (Basic Level) Practice || 1013 数素数 (20 分)
  详细解决方案

PAT (Basic Level) Practice || 1013 数素数 (20 分)

热度:94   发布时间:2023-11-29 11:38:21.0

题目描述:

令 P?i?? 表示第 i 个素数。现任给两个正整数 M≤N≤10?4??,请输出 P?M?? 到 P?N?? 的所有素数。

输入格式:

输入在一行中给出 M 和 N,其间以空格分隔。

输出格式:

输出从 P?M?? 到 P?N?? 的所有素数,每 10 个数字占 1 行,其间以空格分隔,但行末不得有多余空格。

输入样例:

5 27

输出样例:

11 13 17 19 23 29 31 37 41 43
47 53 59 61 67 71 73 79 83 89
97 101 103

解题思路:

这道题也很简单,但PTA判题机的问题就在这道题上表现出来了。

题目解决方式就是一直判断素数,是素数就给计数的变量加一,当变量的数值达到在m到n之间就把素数输出,超过n就停止循环即可。

注意:不能使用while(i++)进行素数判断的循环,这样会直接运行超时;用for循环时也不能设置素数停止,题目会给一个范围(\leq 10^{4})外的测试点,而且我测到了100000都没测出来设在哪里(//?Д/?/),所以只能接受这个判题机的规定了。

下面贴一下我AC后的代码:

#include<stdio.h>
#include<math.h>int gac(int x);int main()
{int i=0, x=0, m, n;scanf("%d%d", &m, &n);for(i=2;;i++){if(gac(i) == 1){x++;if(x>=m && x<=n){printf("%d", i);((x-m+1)%10==0 || x==n) ? printf("\n") : printf("\x20");}}if(x > n)break;}return 0;
}int gac(int x)
{int i;if(x <= 1)return 0;else{for(i=2;i<=sqrt(x);i++)if(x%i == 0)return 0;return 1;}
}

 

  相关解决方案