PAT B1013 数素数

思路：求第M到第N个素数，采用素数筛法，核心思想是从2开始做增量排除4，6，8，10等。

#include<cstdio>

const int maxn = 1000001;
int prime[maxn];
bool not_prime[maxn];
int num;

void FindPrime(int n) {
    for(int i = 2; i < maxn; i++) {
        if(not_prime[i] == false) {
            prime[num++] = i;
            if(num >= n) break;
            for(int j = i + i; j < maxn; j += i) {
                not_prime[j] = true;
            }
        }
    }
}

int main() {
    int M, N;
    scanf("%d %d", &M, &N);
    FindPrime(N);
    int cnt = 0;
    for(int i = M; i <= N; i++) {
        printf("%d", prime[i-1]);
        cnt++;
        if(cnt % 10 != 0 && i < N) printf(" ");
        else printf("\n");
    }
    return 0;
}