1013. 数素数 (20)
令Pi表示第i个素数。现任给两个正整数M <= N <= 104,请输出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程序说明:
定义一个布尔型的素数判别函数,由于大于2的素数一定是奇数,奇数 × 偶数 = 偶数(不是素数),故只需将需要判别的数输入为奇数,且测试时仍只观察能否被奇数整除,加快判别速度
程序中其他循环函数的原理相同。
bool isprime(int num){ //要求num为奇数
if(num==) return false;
if(num==) return true;
int sqt;
sqt = int(sqrt(num));
for(int i =;i<=sqt;i+=) //每次循环加2
if(num%i==) return false;
return true;
}
C++ 代码如下:
#include <bits/stdc++.h>
using namespace std; bool isprime(int num){ //要求num为奇数
if(num==) return false;
if(num==) return true;
int sqt;
sqt = int(sqrt(num));
for(int i =;i<=sqt;i+=) //每次循环加2
if(num%i==) return false;
return true;
}
int main() {
int m,n,p=,count=;
vector<int> num;
cin>>m>>n;
if(m==){
num.push_back();
count=;
}
else {
count=;
for(int i=;i>;i+=){
if(isprime(i)) count++;
if(count==m){
num.push_back(i);
break;
}
}
}
if(num[]==){
for(int i=;count<n;i+=){
if(isprime(i)){
num.push_back(i);
count++;
}
}
}
else{
for(int i=num[]+;count<n;i+=){
if(isprime(i)){
num.push_back(i);
count++;
}
}
}
int sub;
sub=n-m;
while(sub/!=){
for(int i=;i<;i++){
cout<<num[p]<<(i<?" ":"\n");
p++;
}
sub-=;
}
for(int i=p;i<num.size();i++)
cout<<num[i]<<(i<num.size()-?" ":"\n");
system("pause");
return ;
}