C# Short O(N) Solution


  • 0
    L
    public class Solution {
        public int CountPrimes(int n) {
            if(n < 2) return 0;
            bool[] nonPrime = new bool[n];
            for(int i = 2; i <= Math.Sqrt(n); i++)
                if(!nonPrime[i-1])
                    for(int j = i * i; j <= n; j += i)
                        nonPrime[j-1] = true;
            int result = 0;
            for(int k = 2; k < n; k++)
                result += nonPrime[k-1] ? 0 : 1;
            return result;
        }
    }

  • 0
    A

    I don't think it is O(N).. you use 2 for loop


  • 0
    L

    Thanks for pointing it out. This should be O(nLogLogn). I also modified the 2nd loop to starting from (i * i).


  • 0
    A

    // reduce space/cycles by ignoring even numbers

    public class Solution
    {

    public int CountPrimes(int n) {
        if(n<=2) return 0;
        HashSet<int> notPrimes = new HashSet<int>();        
        int cnt = 1; // including 2
        
        // we don't analyze any even numbers
        for(int i=3; i< n; i+=2)
        {
            if(!notPrimes.Contains(i))
               cnt++;
            for (int j=3; i*j <n; j = j+2)   
               notPrimes.Add(i*j);
        }
    
        return cnt;   
    }
    

    }


Log in to reply
 

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