PAT题--1013 数素数
程序员文章站
2024-03-15 15:11:21
...
问题描述:
令 Pi 表示第 i 个素数。现任给两个正整数 M≤N≤10^4 ,请输出 PM 到 PN 的所有素数。
输入格式:
输入在一行中给出 M 和 N,其间以空格分隔。
输出格式:
输出从 PM 到 PN 的所有素数,每 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
“ 开始第四个测试点过不去,猜测可能是常量设置小了,查了下别人做的发现确实是这样,于是在设置 N = 10002 的条件下直接把 MAX设置成很大很大,结果就全员显示段错误,我还以为是MAX 值设太大了,改来改去的,之后才发现原来数组越界的原因是MAX设置很大时,在MAX范围内的素数个数超过了存放素数数组的最大值N,数组存放素数时又是悉数尽收,所以,呕吼完蛋。 我太粗心了。。。”
#include<iostream>
#include<cmath>
using namespace std;
const int N = 11000;
const long long MAX = 110005;
//判断是否为质数
int isPN(long long n){
long long i;
if(n==2||n==3)
return 1;
if(n%2==0||n%3==0)
return 0;
for(i=5;i<=sqrt(n);i+=6)
if(n%i==0||n%(i+2)==0)
return 0;
return 1;
}
int main(){
long long m,n,i,j=0,k=1,p[N];
for(i=2;i<=MAX;i++)
if(isPN(i))
p[k++]=i;
cin>>m>>n;
for(i=m;i<=n;i++){
j++;
if(j%10==0)
cout<<p[i]<<endl;
else if(i!=n)
cout<<p[i]<<" ";
else
cout<<p[i];
}
return 0;
}
上一篇: 算法模板模板(逐渐补充)
下一篇: Python学习第一天