From 700ms to 300ms to 200ms to 100ms to 28ms to 16ms


  • 3

    700ms - most direct and intuitive solution

    class Solution {
    public:
        int countPrimes(int n) {
            if(!n || n==1) return 0;
            vector<bool> numbers(n, true);
            numbers[0] = numbers[1] = false;
            for(int i = 2; i <= sqrt(n); i++)
                for(int j = i*i; j < n; j += i)
                    if(numbers[j]) numbers[j] = false;
            int count = 0;
            for(auto i: numbers)
                if(i) count++;
            return count;
        }
    };
    

    300ms - if it's checked then just skip

    class Solution {
    public:
        int countPrimes(int n) {
            if(!n || n==1) return 0;
            vector<bool> numbers(n, true);
            numbers[0] = numbers[1] = false;
            for(int i = 2; i <= sqrt(n); i++)
                if(numbers[i])
                for(int j = i*i; j < n; j += i)
                       numbers[j] = false;
            int count = 0;
            for(int i = 0; i < n; ++i)
                if(numbers[i]) count++;
            return count;
        }
    };
    

    200ms - actually half of the numbers can just be ignored since they can divided by 2;

    class Solution {
    public:
        int countPrimes(int n) {
            if(n < 3) return 0;
            vector<bool> numbers(n, true);
            numbers[0] = numbers[1] = false;
            for(int i = 3; i <= sqrt(n); i += 2)
                if(numbers[i])
                for(int j = i*i; j < n; j += i)
                       numbers[j] = false;
            int count = 1;
            for(int i = 3; i < n; i += 2)
                if(numbers[i]) count++;
            return count;
        }
    };
    

    100ms - using array to replace vector and meantime move twice quicker than before since we've removed even numbers.

    class Solution {
    public:
        int countPrimes(int n) {
            if(n < 3) return 0;
            bool *numbers = new bool[n];
            memset(numbers, 1, sizeof(bool)*n);
            numbers[0] = numbers[1] = false;
            for(int i = 3; i <= sqrt(n); i += 2)
                if(numbers[i])
                for(int j = i*i, k = i<<1; j < n; j += k)
                       numbers[j] = false;
            int count = 1;
            for(int i = 3; i < n; i += 2)
                if(numbers[i]) count++;
            return count;
        }
    };
    

    16ms - merge these two loops

    class Solution {
    public:
        int countPrimes(int n) 
        {
            if(n < 3) return 0;
            bool *numbers = new bool[n];
            memset(numbers, 1, sizeof(bool)*n);
            int count = n/2;
            for(int i = 3; i <= sqrt(n); i += 2)
                if(numbers[i])
                for(int j = i*i, k = i<<1; j < n; j += k)
                {  
                    if(numbers[j]) count--;
                       numbers[j] = false;
                }
            return count;
        }
    };
    

    This is the best I can do, if you have better solutions please comment below! Thanks!


Log in to reply
 

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