Java solution trade off time cost for space cost compared to Sieve of Eratosthenes.


  • 0
    L

    //maybe time cost higher than Sieve of Eratosthenes, but only need to store primes, space cost is O(primes) rather than O(n)

    //Idea is to check if N is prime, we only need to check whether N has the prime factors less than sqrt(N). Because if it has non-prime factor, it must has corresponding prime factor.

    public class Solution {
        public int countPrimes(int n) {
            int count = 0;
            List<Integer> primes = new ArrayList<Integer>();
            for(int i=2;i<n;i++){
                boolean isPrime = true;
                for(int j=0;j<primes.size();j++){
                    if(primes.get(j)*primes.get(j)>i) break;
                    if(i%primes.get(j)==0){
                        isPrime = false;
                        break;
                    }
                }
                if(isPrime){
                    primes.add(i);
                    count++;
                }
            }
            return count;
        }
    }

Log in to reply
 

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