Short C++ Sieve of Eratosthenes solution


  • 43
    D
    class Solution {
    public:
        int countPrimes(int n) {
            vector<bool> prime(n, true);
            prime[0] = false, prime[1] = false;
            for (int i = 0; i < sqrt(n); ++i) {
                if (prime[i]) {
                    for (int j = i*i; j < n; j += i) {
                        prime[j] = false;
                    }    
                }    
            }
            return count(prime.begin(), prime.end(), true);
        }
    };

  • 1
    I

    can you explain how to come up with this genius idea?you are smarter than too many people


  • 1
    O

    it is the Sieve of Eratosthenes algorithm, wiki: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes


  • 0
    H

    Python3 Solution

    class Solution(object):
        def countPrimes(self, n):
            """
            :type n: int
            :rtype: int
            """
            if n < 2:
                return 0
            prime = [True] * n
            prime[0] = prime[1] = False
            for i in range(int(math.ceil(n**0.5))):
                if prime[i]:
                    for j in range(i**2, n, i):
                        prime[j] = False
            return prime.count(True)
    

  • 1

    @deck seems like maintaining a counter would be better than iterating through the primes at the end


  • 0
    A

    why I am getting wrong answer? my code

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

  • 1
    W

    @abhinav_smart
    You should notice this linememset(a,true,sizeof(a));, here sizeof(a) actually equals to 4, which is the size of a pointer. I suppose that it should be written as memset(a, true, sizeof(a)*n)
    Hope it will help. :)


  • 0
    A

    @wysqh Thanks Brother


Log in to reply
 

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