7-294 筛法求素数（埃式筛、欧拉筛）
素数是仅仅能被它本身和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 #include <stdio.h>
#include <stdlib.h>
#include <string.h#define N (int)1e5+9 // 1e5+9为浮点类型
int pri[N]; // 0为素数，1为合数 // 1.埃式筛法
int main(void)
{int n;scanf("%d", &n);while(n--){int cnt=0;memset(pri,0,sizeof(pri));int x,y;scanf("%d %d",&x,&y);// 模板for (int i = 2; i <= y/i; i++) {if (!pri[i]) { // i为素数for (int j = i * i; j <= y; j += i) pri[j] = 1; // 筛掉i的倍数}}for(int i=2;i<=y;i++){if(!pri[i] && i>=x && i<=y){cnt++;printf("%d ",i);}}if(cnt)printf("\n");elseprintf("None\n");}return 0;
}#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define N (int)1e5+9
int pri[N]; // 0为素数，1为合数
int primes[N],pp=0;
// 2.欧拉筛法
int main(void)
{int n;scanf("%d", &n);while(n--){int cnt=0,ans=0;pp=0;memset(pri,0,sizeof(pri));int x,y;scanf("%d %d",&x,&y);// 模板for(int i=2;i<=y;i++){if(!pri[i]) primes[++pp]=i,cnt++;for(int j=1;j<=pp && primes[j]*i<=y;j++){pri[primes[j]*i]=1;if(i%primes[j]==0) break;}}for(int i=1;i<=cnt;i++) {if(primes[i]>=x && primes[i]<=y){printf("%d ",primes[i]);ans++;}}if(ans)printf("\n");elseprintf("None\n");}return 0;
}