Sieve of Euler By C++


  • 0

    Sieve of Euler, its runtime complexity is O(n), better than Sieve of Eratosthenes(n * log(log(n))).

    //C++ 14 
    const int MAXN = 1e7;
    int primes[MAXN << 1];
    bool isPrime[MAXN];
    class Solution {
    public:
        int countPrimes(int n) {
            int primeCnt = 0;
            memset(isPrime, true, sizeof(isPrime));
            isPrime[0] = isPrime[1] = false;
            for (int i = 2; i < n; ++i) {
                if (isPrime[i])
                    primes[primeCnt++] = i;
                for (int j = 0; j < primeCnt && primes[j] * i < n; ++j) {
                    isPrime[primes[j] * i] = false;
                    if (!(i % primes[j]))
                        break;
                }
            }
            return primeCnt;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.