204. Count Primes (Easy)

https://leetcode.com/problems/count-primes/

Count the number of prime numbers less than a non-negative number, n.

Example:

Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Solutions

class Solution {

    // Thinking transformation, tag all the non-primes

    public int countPrimes(int n) {

        // Used to keep all the non-primes.
        boolean[] primeOrNot = new boolean[n];
        Arrays.fill(primeOrNot, true);

        // must be <= n/2, not < n/2
        for (int i = 2; i <= n / 2; i++) {
            for (int j = 2; i * j < n; j++) {
                primeOrNot[i * j] = false;
            }
        }

        int ans = 0;
        for (int i = 2; i < n; i++) {
            if (!primeOrNot[i]) {
                continue;
            }

            ans++;
        }

        return ans;
    }
}

Incorrect Solutions

1.

class Solution {

    // Still hardly suffice for efficiency requirements.

    public int countPrimes(int n) {

        // Used to keep all the non-primes.
        boolean[] primeOrNot = new boolean[n];
        Arrays.fill(primeOrNot, true);

        for (int i = 2; i < n; i++) {
            if (!primeOrNot[i]) {
                continue;
            }

            int x = (int) Math.sqrt(i);

            for (int j = 2; j <= x; j++) {
                if (i % j != 0) {
                    continue;
                }

                primeOrNot[i] = false;

                break;
            }
        }

        int ans = 0;
        for (int i = 2; i < n; i++) {
            if (!primeOrNot[i]) {
                continue;
            }

            ans++;
        }

        return ans;
    }
}

2.

class Solution {

    // Using Set structure to keep the non-prime elements will dramatically slow down the speed.

    public int countPrimes(int n) {

        // Used to keep all the non-primes.
        Set<Integer> primeOrNot = new HashSet<>();

        for (int i = 2; i < n; i++) {
            for (int j = 2; j * j <= i; j++) {
                if (i % j != 0) {
                    continue;
                }

                primeOrNot.add(i);

                break;
            }
        }

        int ans = 0;
        for (int i = 2; i < n; i++) {
            if (primeOrNot.contains(i)) {
                continue;
            }

            ans++;
        }

        return ans;
    }
}

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2020-03-21 15:19:41

results matching ""

    No results matching ""