当前位置: 首页 > 工具软件 > Sieve > 使用案例 >

Sieve of Eratosthenes算法实现

赵渊
2023-12-01

这是个很古老的求素数的算法,其实现的方法就是从2开始,循环遍历数组,有倍数的就置为0。

#include <iostream>
#include <vector>
#include <cmath>
#define N 100
using namespace std;
int main(void) {
    vector<int> ar;
    for (int i = 0; i < N; i++) {
        ar.push_back(i);
    }
    for (int i = 2; i < ar.size(); i++) {
        int j = i;
        while (j < ar.size()/2) {
            ar[j*2] = 0;
            j*=2;
        }
    }
    for (int i = 2; i < ar.size(); i++)
        if (ar[i] != 0)
            cout << ar[i] << " ";
    cout << endl;
}

输出:

wang@wang:~/workspace$ ./a.out
2 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99

 类似资料: