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

链接：1013. 数素数 (20)

题意

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

分析

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

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

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

代码

#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; }

小结

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