LeetCode: Count Primes

Way 1: O(n^1.5) cannot pass leetcode test, too long time

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution { public: static bool isPrime(int n){ if(n<=1) return false; for(int i=2;i*i<=n;i++){ //Notice <=n when testing whether n is prime if(n%i==0) return false; } return true; } static int countPrimes(int n) { if(n<=1) return 0; int count=0; for(int i=2;i<n;i++){ if(isPrime(i)) { count++; } } return count; } };

Way 2: O(n*loglogn) Sieve of Eratostrenes

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

class Solution { public: int countPrimes(int n) { bool* isPrime=new bool[n]; for(int i=0;i<n;i++) isPrime[i]=true; //for(int i=2;i<=sqrt(n);i++){ for(int i=2;i*i<n;i++){ //since n is not included, condition equals i*i<=(n-1) if(isPrime[i]) { for(int j=i*i;j<n;j=j+i){ isPrime[j]=false; } } } int count=0; for(int i=2;i<n;i++){ if(isPrime[i]) count++; } delete[] isPrime; return count; } };

Reference: https://leetcode.com/problems/count-primes/