筛法求素数 (20分)

素数 (20分)"/>

筛法求素数 (20分)

题干：
素数是仅仅能被它本身和1整除的任何整数。筛法求素数是一种查找素数的方法。它的算法如下：

1、创建一个数组，并将所有元素初始化为1（真）。具有素数下标的数组元素将保持为1，而其它数组元素最终将被设置为0。

2、从数组下标2开始，每次找到一个值是1的数组元素时，在数组的剩余部分中循环，并将值为1的元素的下标整数倍的所有元素设置为0。对于数组下标2，数组中所有2以上的而且是2的整数倍的元素都将这是为0（下标4、6、8、10等等）。对于数组下标3，数组中所有3以上，而且是3的整数倍的元素都将设置为0（下标6、9、12、15等等）。

当这个过程结束时，仍然为1的数组元素的下标是一个素数。然后就可以输出这些素数。

编写一个程序，输出区间[m, n]之间的所有素数。

输入格式:

输入的第一行是一个整数k，表示以后会有k次查询。 后面的k行中，每行2个整数m和n。
输入保证 2 <= m <= n <= 100000。

输出格式:

对每一行的m和n，把闭区间[m, n]之间的所有素数输出到一行。每个数之间以空格隔开。若区间内没有素数，输出None

输入样例:

6
2 20
3 3
5 15
11 32
121 126
100 200

**
输出样例:**

2 3 5 7 11 13 17 19 
3 
5 7 11 13 
11 13 17 19 23 29 31 
None
101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 

code：

#include <bits/stdc++.h>
using namespace std;
#define MAX 100010void sShuSX(int m, int n) {int s[MAX];for(int i = 0; i < MAX; i++) {s[i] = 1;}for(int i = 2; i <= n; i++) {if(s[i]) {for(int j = i + 1; j <= n; j++) {if(j % i == 0) {s[j] = 0;}}}}int o = 0;for(int i = m; i <= n; i++) {if(s[i]) {cout << i<< " ";o = 1;}}if(!o) {cout << "None";}cout << "\n";
}int main() {int k, m, n;cin >> k;while(k--) {cin >> m>> n;sShuSX(m, n);}
}