PAT-B] 1013. 数素数 [数论]

链接：1013. 数素数 (20)

题意

输入两个数 M, N。
然后输出第M个到第N个素数。

分析

由于这里的M和N都是表示的第几个素数。
所以我们必须先把素数列出来。
（列素数的方法有很多，这里就不一一介绍了）

列完素数之后，就输出对应范围内的素数就好了。

要注意的是：这里的第M个到第N个素数也是要输出的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <cstdio>
#define MAX 200000
int sf[MAX];    // 下标对应的数字是不是素数, 1:非, 0:是
int ss[10005];  // 按升序存放素数
int idx = 0;    // 素数数组的下标
int main()
{
    int M, N;
    for( int i = 2; i <= MAX; i++ ){    // 打素数表
        if( sf[i] == 0 ){
            ss[idx++] = i;
            if( idx > 10000 )   break;
            if( i < 2000 ){
                for( long long j = i * i; j <= MAX; j += i ){
                    sf[j] = 1;  // 素数的倍数标注为非素数
                }
            }
        }
    }
    while( ~scanf( "%d%d", &M, &N ) ){
        int i = M - 1;
        if( i < 0 ) i++;
        printf( "%d", ss[i++] );
        for( int j = 1; i < N; j++ ){
            if( j == 10 ){
                puts( "" );
                j = 0;
            }
            else    printf( " " );
            printf( "%d", ss[i++] );
        }
        puts( "" );
    }
    return 0;
}

小结

题目并不难，但求素数的方法是很值得去多查一查的。

数论
PAT-B, 数论