埃拉托斯特尼篩法

快速查找素數(shù)

時間限制：1000?ms ?|? 內(nèi)存限制：65535?KB難度：3描述

現(xiàn)在給你一個正整數(shù)N，要你快速的找出在2.....N這些數(shù)里面所有的素數(shù)。

輸入

給出一個正整數(shù)數(shù)N(N<=2000000)
但N為0時結(jié)束程序。
測試數(shù)據(jù)不超過100組

輸出

將2~N范圍內(nèi)所有的素數(shù)輸出。兩個數(shù)之間用空格隔開

樣例輸入

5 10 11 0

樣例輸出

2 3 5 2 3 5 7 2 3 5 7 11

來源

經(jīng)典題

上傳者

路過這

思路參見wiki的解釋。復(fù)雜度是接近線性的。

#include<stdio.h> #include<string.h> #define MAX 2000001 int all[MAX]; int N,i,j,s; int main() {memset(all,1,sizeof(all));for(i=2;i<=MAX;i++)if(all[i])for(j=i+i;j<=MAX;j+=i)all[j]=0;while(scanf("%d",&N),N){for(i=2;i<=N;i++)if(all[i])printf("%d ",i);printf("\n");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的埃拉托斯特尼筛法 快速查找素数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。