LeetCode204-Count Primes

ぶんせき
この問題はnより小さいすべての質量数を求めることに相当し、プログラミングの美の中で1組の質量数を求めるアルゴリズムを見たことがある.エラドセふるい法と呼ばれ、時間複雑度はO(nloglogn)しかない.これはかなり良いアルゴリズムである(1からn-1まで質量数をそれぞれ判断すれば、時間複雑度はO(nsqrt(n))である.エラドセふるい法の手順:2からnまでの集合G={2,3,4,...,n}を確立し、集合から最小の数Aを取り出すたびに、この数が質量数である.次に、1<=times<=n/Aの数A*timesをセットから削除します.新しい集合G′が得られ,集合が空になるまで上記の手順を繰り返し,すべての質量数を取り出した.例えば、1つの集合{2,3,4,...,12}:stp 1:最小値は2であり、2を取り出して2,4,6,8,10,12を削除し、集合は{3,5,7,9,11}となる.stp 2:最小値は3で、3を取り出して3,6,9を削除し、集合は{5,7,11}...最後に,質量数2,3,5,7,11を得た.
に注意

最初はunorderedを使いましたsetは、1つの数が削除されたかどうかをマークし、メモリが要求を超えて使用されます.後にbool配列を用いてACを記録した.

は、n以下ではなくn未満であることに留意される.

class Solution {
public:
    int countPrimes(int n) {
        bool isDeleted[n];
        for (unsigned i = 0; i < n; ++i)
            isDeleted[i] = false;

        int count = 0;
        for (unsigned i = 2; i < n; ++i) {
            if (!isDeleted[i]) {
                ++count;
                for (unsigned times = 1; i * times <= n; ++times) {
                    isDeleted[i*times] = true;
                }
            }
        }
        return count;
    }
};