[数据结构与算法]PAT乙级 1013数素数

一.题目描述

令?P?i???表示第?i?个素数。现任给两个正整数?M≤N≤10?4??，请输出?P?M???到?P?N???的所有素数。

输入格式：

输入在一行中给出?M?和?N，其间以空格分隔。

输出格式：

输出从?P?M???到 P?N?? 的所有素数，每 10 个数字占 1 行，其间以空格分隔，但行末不得有多余空格。

二.题解

易错点：题目要求输出PM到PN间的所有素数，Pi为第i个素数，而不是从M到N之间的素数。

思路：用变量num来表示第num个素数，从而判断是否输出以及什么时候结束循环。

三.代码

#include<bits/stdc++.h>
using namespace std;
bool isprime(int a)
{
    int flag=1;
    for(int j=2;j<a;j++)
        {
            if(a%j==0)
                flag=0;
        }
    return flag;
}
int main()
{
    int m,n,num=0;
    cin>>m>>n;
    for(int i=2;num<n;i++)      //其中的结束条件是已经输出玩第n个素数
    {
        if(isprime(i))
        {
            num++;
            if(num==m)          //第一项前无空格
                cout<<i;
            else if(num>m)
                cout<<" "<<i;
        }
    }
}