求0-2000内的所有质数(筛选法)

winston

核心算法:

我们先设保存整数0~N的数组为sieve[N+1]，用“逐步求精”的方法来得出算法：
[定理1]若比素数P小的所有素数的倍数均已从sieve中删去，且P*P > N,则sieve = primes(2…N)。其中：primes(2..N)表示2..N之间所有的素数。
引用:http://blog.csdn.net/zzjjzzgggg/article/details/2493957

Code://Func.h

2. #include "stdafx.h"
3. #include <iostream>
5. using std::cout;
6. using std::endl;
8. void PrintNums(int num)
9. {
10.         bool *arr=new bool[num];
12.         //初始化数组
13.         for(int i=0;i<num;i++)
14.         {
15.                 arr[i]=true;
16.         }
17.         //去非素数
18.         for(int i=2;i<=num;++i)
19.         {
20.                 if(arr[i-1]==true)
21.                 {
22.                         for(int j=2*i;j<=num;j+=i)
23.                         {
24.                                 arr[j-1]=false;
25.                         }
26.                 }
27.         }
28.         //打印素数
29.         for(int i=0;i<num;i++)
30.         {
31.                 if(arr[i]==true)
32.                 {
33.                         cout<<i+1<<endl;
34.                 }
35.         }
36. }

复制代码

作者：xufei96 发表于2012-1-20 10:10:28 原文链接