题目描述:
令 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循环时也不能设置素数停止,题目会给一个范围()外的测试点,而且我测到了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;}
}