Java accepted solution put previous primes in ArrayList


  • 0
    O
        public class Solution {
            public int countPrimes(int n) {
                ArrayList<Integer> primes = new ArrayList<Integer>();
                if(n < 3){
                    return 0;
                }
                int count = 1;
                primes.add(2);             // first put 2 into the prime list
                for(int i = 3; i < n; i = i+2){    // only  the odds
                    if(isPrime(i,primes)){
                        primes.add(i);
                        count++;
                    }
                }
                return count;
            }
            private boolean isPrime(int i, ArrayList<Integer> primes){
                if(i != 5 && i % 5 == 0){
                    return false;
                }
                int j = 0;
                while(primes.get(j) <= Math.sqrt(i)){ 
    /*only need to test the prime in the list which less than sqrt of i*/      
                    if(i % primes.get(j) == 0){
                        return false;
                    }
                    j++;
                }
                return true;
            }
        }

  • 0
    G

    Why are you doing special handling for 5? It still works without that.


Log in to reply
 

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