快速查找素数
时间限制：
1000 ms | 内存限制：
65535 KB
难度：
3
描述
现在给你一个正整数N，要你快速的找出在2.....N这些数里面所有的素数。
输入
给出一个正整数数N(N<=2000000)
但N为0时结束程序。
测试数据不超过100组
输出
将2~N范围内所有的素数输出。两个数之间用空格隔开
样例输入
5
10
11
0
样例输出
2 3 5
2 3 5 7
2 3 5 7 11
#include<stdio.h>// AC
#include<math.h>
#include<string.h>
#define N 2000000 +10
char arr[N]; //int的数组会超时
int prime()
{
memset(arr,0,sizeof(arr));
arr[0]=arr[1]=1;
int n=sqrt(N)+1;
for(int i=2;i<=n;i++){
if(!arr[i]){
for(int j=i+i;j<=N;j+=i){
arr[j]=1;
}
}
}
}
int main()
{
prime();
int n;
while(~scanf("%d",&n),n){
for(int i=2;i<=n;i++){
if(!arr[i])
printf("%d ",i);
}
printf("\n");
}
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-969464.html
