PAT 1013 数素数

1013. 数素数 (20)

时间限制 100 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standard 作者 CHEN, Yue

令P_i表示第i个素数。现任给两个正整数M <= N <= 10⁴，请输出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

思路：这一题有两种做法 (1)用普通的方法来做，就是从2开始一次找素数，然后根据要求来输出要输出的素数 (2)先找出前1W个素数，然后根据要求输出就行了 这里我用的是普通的方法，有一点要注意，普通的方法如果不优化算法，就会提示输出超限。 第一个是C代码，第二个是C++代码

#include <stdio.h> #include <math.h> int prime(int x); int main() { int m,n,a,j=1,k=1; scanf("%d %d",&m,&n); for (int i=2;;i++) { a=prime(i); if (a==1) { if (j==n&&j>=m) { printf("%d",i); break; } else if (k==0&&j>=m) { printf("%d\n",i); k++; } else if (j>=m) { printf("%d ",i); k++; } j++; } } } int prime(int x) { int n=0; if (x%2==0&&x!=2) return 0; for (int i=2;i<=(int)sqrt(x);i++) { if (x%i==0) { n=1; break; } } if (n==1) return 0; else return 1; }

******************************************************************************************

#include <iostream> #include <math.h> using namespace std; int prime(int x); int main() { int m,n,a,j=1,k=1; cin>>m>>n; for (int i=2;;i++) { a=prime(i); if (a==1) { if (j==n&&j>=m) { cout<<i; break; } else if (k==0&&j>=m) { cout<<i<<endl; k++; } else if (j>=m) { cout<<i<<" "; k++; } j++; } } } int prime(int x) { int n=0; if (x%2==0&&x!=2) return 0; for (int i=2;i<=(int)sqrt(x);i++) { if (x%i==0) { n=1; break; } } if (n==1) return 0; else return 1; }