Posted on Jun 15, 2020

エラトステネスの篩 (Sieve of Eratosthenes)

code

最近JavaScriptでPriorityQueueとかなくて悲しいことが多いのでさけがちです。今回はC++にしました。

class Solution {
 public:
  int countPrimes(int n) {
    int count = 0;
    if (n < 2) {
      return count;
    }
    vector<bool> visit(n);
    for (int i = 2; i < n; i++) {
      if (visit[i]) {
        continue;
      }
      count++;
      int v = i;
      while (v <= n) {
        visit[v] = true;
        v += i;
      }
    }
    return count;
  }
};