Count Primes

Source

• leetcode: Count Primes

Count the number of prime numbers less than a non-negative number, n.

Java

//Sieve of Eratosthenes
public class Solution {
    public int countPrimes(int n) {
        int res=0;
        boolean[] used = new boolean[n];

        for(int i=2; i<n; i++){
            if(!used[i]){
                for (int j = 2*i; j<n; j+=i) {
                    used[j]=true;
                }
            }
        }
        for(int i=2; i<n; i++){
            if (!used[i]) {
                res++;
            }
        }
        return res;        
    }

    //暴力解法, 但是过不了大数据
    // public  int countPrimes(int n) {
    //     int count = 0;
    //     for(int i=2;i<n;i++){
    //         if(isPrime(i))
    //             count++;
    //     }
    //     return count;
    // }

    // public  boolean isPrime(int n){
    //     for(int i=2;i<=Math.sqrt(n);i++)
    //         if(n%i == 0)
    //             return false;
    //     //System.out.println(n + " is a prime");
    //     return true;
    // }    
}

Python

class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        result=0
        used = [False] * n

        #这里一定要用xrange不能用range 否则memory overflow
        for i in xrange(2, n): 
            if used[i]==False:
                for j in xrange(2*i, n, i):
                    used[j]=True

        for i in xrange(2, n):
            if used[i] is False:
                result+=1

        return result