c/c++补完计划(三): 素数统计

bool isPrime(int i) {
    for (int j = 2; j * j <= i; ++j) {
        if (i % j == 0)return false;
    }

    return true;
}

int countPrimes(int n) {
    if (n < 2) {
        return 0;
    }

    int count = 0;
    for (int i = 2; i < n; ++i) {
        if (isPrime(i)) {
            ++count;
        }
    }

    return count;
}

int countPrimes(int n) {
    if (n < 2) {
        return 0;
    }

    vector<bool> tmp(n, false);
    vector<int> prime;

    for (int i = 2; i < n; ++i) {
        if (!tmp[i]) {
            prime.push_back(i);
        }
        for (int j = 0; j < prime.size() && i * prime[j] < n; ++j) {
            tmp[i * prime[j]] = true;
            if (i % prime[j] == 0) break;
        }
    }

    return prime.size();
}