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

  • 0

    //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;
                        isPrime = false;
            return count;

Log in to reply

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