欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

PAT题--1013 数素数

程序员文章站 2024-03-15 15:11:21
...

问题描述:
令 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

“ 开始第四个测试点过不去,猜测可能是常量设置小了,查了下别人做的发现确实是这样,于是在设置 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;
}