Sieve of Eratosthenes algorithm, java solution.


  • 0
    Z
    public class Solution {
        public int countPrimes(int n) {
            if (n < 3) return 0;
            boolean[] primes = new boolean[n];
            int cnt = 0;
            for (int i = 0; i < n; i++) primes[i] = true;
            for (int k = 2; k < (float) n / k; k++)
            {
                if (primes[k])
                {
                    for (int i = k; i < (float) n / k; i++) primes[i * k] = false;
                }
            }
            for (int i = 2; i < n; i++) if (primes[i]) cnt++;
            return cnt;
        }
    }
    

Log in to reply
 

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