这是个很古老的求素数的算法,其实现的方法就是从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