My Java AC solution


  • 1
    H

    The idea is very simple. instead of find each primes, remove all composite numbers from 2~n.

    public class Solution {
    public int countPrimes(int n) {
        boolean[] exist = new boolean[n];
        Arrays.fill(exist, true);
        for (int i = 2; i < n; i++) {
            if (exist[i]) {
                int idx = i;
                for (int j = 2; idx * j < n; j++) {
                    exist[idx*j] = false;
                }
            }
        }
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (exist[i]) {
                count++;
            }
        }
        return count;
    }
    

    }


  • 3

    It's a clear code : ).

    I think the second loop could be removed:

    public class Solution {
        public int countPrimes(int n) {
            boolean[] exist = new boolean[n];
            Arrays.fill(exist, true);
            int count = 0;
            for (int i = 2; i < n; i++) {
                if (exist[i]) {
                    count++;
                    for (int j = 2; i * j < n; j++) {
                        exist[i*j] = false;
                    }
                }
            }
            return count;
        }
    }

Log in to reply
 

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