Simple Java O(n) Solution


  • -2
    X

    If we encounter a prime number mark all its multiples to non-prime.

    public class Solution {
        public int countPrimes(int n) {
            if(n<1) return 0;
            boolean[] primeArray = new boolean[n+1];
            primeArray[1] = true;
            for(int i=2; i<primeArray.length; i++) {
                if(primeArray[i]==false) {
                    for(int j=2; i*j<n+1;j++) 
                        primeArray[i*j] = true;
                }
            }
            int count=0;
            for(int i=1; i<primeArray.length-1; i++)
                if(primeArray[i]==false) count++;
            return count;
        }
    }

  • 0
    X

    Nice code but I guess it is a little slower than O(n) because same composite number could be visited multiple times.
    Plus why you count prime from 1 at last? Looks very confusing to me.


Log in to reply
 

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