快速查找素數

時間限制：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

cpp：

#include<stdio.h> #define N 2000002 int prime[N]={0,0}; int main() {int i,j,n=0;for(i=2;i<N;i++) prime[i]=1;for(i=2;i<N;i++){if(prime[i]==1){for(j=2*i;j<N;j=j+i)prime[j]=0;}}while(scanf("%d",&n)!=EOF){if(n>1){for(j=2;j<=n;j++)if(prime[j]==1)printf("%d ",j);printf("\n"); }}return 0; }
篩法：一種簡單檢定素數的算法。

1.求100之內的素數。

思想：

用篩法求素數的基本思想是：把從1開始的、某一范圍內的正整數從小到大順序排列， 1不是素數，首先把它篩掉。剩下的數中選擇最小的數是素數，然后去掉它的倍數。依次類推，直到篩子為空時結束。如有： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 1不是素數，去掉。剩下的數中2最小，是素數，去掉2的倍數，余下的數是： 3 5 7 9 11 13 15 17 19 21 23 25 27 29 剩下的數中3最小，是素數，去掉3的倍數，如此下去直到所有的數都被篩完，求出的素數為： 2 3 5 7 11 13 17 19 23 29

#include<stdio.h> #include<math.h> int main() {int a[101],i,j;for(i=1;i<=100;i++)a[i]=i;a[1]=0;for(i=2;i<=100;i++)if(a[i]!=0)for(j=i+1;j<=100;j++)if(a[j]!=0&&a[j]%a[i]==0)a[j]=0;for(i=2;i<=100;i++)if(a[i]!=0)printf("%d ",a[i]);return 0; }

總結

以上是生活随笔為你收集整理的nyoj187 快速查找素数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。