Count Primes(C++) by yangchaojie


  • 0
    Y

    class Solution {
    public:
    int countPrimes(int n) {
    int counter_number = 0;
    if(n == 0 | n==1)
    counter_number = 0;
    bool *Del = new bool[n];
    Del[2] = false;

        for(int i = 3;i <= n;i++)
        {
            if(i % 2 == 0)
                Del[i] = true;
            else
                Del[i] = false;
        }
        
        for(int i = 3;i <= n;i += 2)
        {
            if(!Del[i])
            {
                if(i * i > n)
                    break;
                for(int j = 3; i*j < n;j++)
                {
                    Del[i*j] = true;
                }
            }
        }
        for(int i = 2;i < n;i++)
        {
            if(!Del[i])
                counter_number += 1;
        }
        return counter_number;
            
    }
    

    };


Log in to reply
 

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