Slow Java solution with memoization (~600 ms)


  • 0
    W
    public class Solution {
        List<Integer> primesFound;
        public Solution(){
            primesFound = new ArrayList<Integer>();
        }
    
        private boolean isPrime(int x){
            int j = 2;
            int prime;
            for(int i = 0; j < x; i++){
                prime = primesFound.get(i).intValue();
                j = prime * prime;
                if(x % prime == 0) return false;
            }
            primesFound.add(new Integer(x));
            return true;
        }
    
        public int countPrimes(int n) {
            int count = 0;
            for(int i = 2; i < n; i++){
                if(isPrime(i)) count++;
            }
            return count;
        }
    }
    

    This approach ensures that only primes are used when testing for factors in isPrime.


Log in to reply
 

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