空间换取时间算法:筛法求素数（C++）_c++ 质数表 空间换时间

筛法求素数

// 筛法求素数
// 把2到n中的所有的数都列出来，从2开始划掉2内所有的倍数，
// 然后每次从下一个剩下
// 的数开始（必然是素数），划掉其n内所有的倍数。最后剩下的数就都是素数。

// 空间换时间，加快计算速度

//设置一个isprime数组，isprime[i]的值是1就表示i是素数
// 划掉k的倍数就是把 isPrime[2k]、isPrime[3k]……置成0
// 最后检查数组，输出数组值为1的i

#include<iostream>
using namespace std;
#define MAX_NUM 100000
char isPrime[MAX_NUM+10];
// 防止数组越界，因为i就是表示一个数
// 用char类型节省空间
int main(){
    for(int i=2;i<=MAX_NUM;i++){
        isPrime[i]=1;
    }
    for(int i=2;i<MAX_NUM;i++){
        if(isPrime[i]){
            for(int j=2*i;j<=MAX_NUM;j+=i){
                isPrime[j]=0;
            }
        }
    }
    for(int i=2;i<=MAX_NUM;i++){
        if(isPrime[i]){
            cout<<i<<endl;
        }
    }
    return 0;

}

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