C++ solution O(n/ln(n)) space


  • 0
    T

    It seems that all solutions I saw so far used O(n) space. So I came to share my slower (306ms) yet the less space-consuming solution (O(n/ln(n)). See the wiki page prime number theorem for why the space needed is O(n/ln(n)).

    Logic: If a number is not a prime, then it can be divided by at least a prime. Thus, we maintain a vector of primes. Every time a number cannot be divided by the primes we know currently, we add it in.

    class Solution {
    public:
        int countPrimes(int n) {
            vector<int> primes;
            for (int i = 2; i < n; ++i) {
                bool isPrime = true;
                int sqrt_i = sqrt(i);
                for (int prime : primes) {
                    if (i % prime == 0) {
                        isPrime = false;
                        break;
                    } else if (prime > sqrt_i) {
                        break;
                    }
                }
                if (isPrime) {
                    primes.push_back(i);
                }
            }
            return primes.size();
        }
    };
    

    Any advice to improve the code would be appreciated. Many thanks.
    TL


Log in to reply
 

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