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

思路：使用筛选法，现将素数筛选出来，然后对其进行操作。
测试点4：是个比较大的数据。

#include <iostream>
#include <cmath>
using namespace std;

int isprime(int n){
    int i;
    for(i=2;i<=(int)sqrt((double)n);++i){
        if(n%i==0) return 0;
    }
    return 1;
}

int main()
{
    int M,N,k=0;
    cin>>M>>N;
    int a[110000];
    
    for(int i=2,j=0;i!=110000;++i){
        if(isprime(i)){
            a[j++]=i;
        }
        
    }
    
    for(int i=M-1;i<N; ++i){
        if(k<9&&i!=N-1){
            cout<<a[i]<<" ";
            k++;
        }
        else if(k==9&&i!=N-1) {
            cout<<a[i]<<endl;
            k=0;
        }
        else if(i==N-1) {
            cout<<a[i];
        }
    }
    
    return 0;
}

筛选法：
先把N个自然数按次序排列起来。1不是质数，也不是合数，要划去。第二个数2是质数留下来，而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5，把5留下，再把5后面所有能被5整除的数都划去。这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数。