素数—埃式筛法

埃式筛法

思路

 利用当前已经确定的素数筛选掉非素数的自然数，然后向后选择没有被筛选的自然数，即素数，重复上述操作。

实现

打印 [1, 100] 区间的素数

#include <iostream>
#include <vector>
using namespace std;

int main(){
  vector<int> prime;
  vector<bool> isPrime(110, true);

  for (int i = 2; i <= 100; i ++ ) {
    if (isPrime[i]) prime.push_back(i);
    for (int j = 2; i * j <= 100; j ++ ) 
      isPrime[i * j] = 0;
  }

  for (auto &p : prime) cout << p << " " ;
  cout << endl;

  return 0;
}