快速查找素数
时间限制：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 <iostream>
#include<stdio.h>
#include <cstring>
using namespace std; const int MAXN = ;
bool u[MAXN];
int prime[MAXN], cnt = ;
void primer(){
memset(u, true, sizeof(u));
for(int i=; i<MAXN; ++i){
if(u[i]) prime[cnt++] = i;
for(int j=; j<cnt && i*prime[j]<MAXN; ++j){
u[i*prime[j]] = false;
if( == i%prime[j]) break;
}
}
}
//
int getnum(int n){
int left = ,right = cnt-;
int middle=(left+right)/ ;
while(prime[middle]!=n&&right>=left ){
if(n<prime[middle]) right = middle-;
else left= middle+;
middle = (left+right)/;
}
return middle;
} int main(){
int n; primer();
while(){
scanf("%d",&n);
if(n==) break;
for(int i=;i<getnum(n )+;i++ ){
printf("%d ",prime[i] ) ;
}
printf("\n");
}
return ;
}下面曝一种其他同学的写法：也是筛法，但是比较单一，比较简单，但是却能AC。
#include<stdio.h> int main(){
int n,i,s,j;
bool a[]={};
a[]=;a[]=; //并没有考虑可能重复筛选的数字
for(i=;i<;i++){
if(a[i]==){
for(j=i+i;j<=;j=j+i)
a[j]=;
}
} while(scanf("%d",&n)!=EOF&&n!=){
s=;
for(i=;i<=n;i++){
if(a[i]==){
s++;
if(s==) printf("%d",i);
if(s>) printf(" %d",i);
}
}
printf("\n");
}
return ;
}