【Leetcode】204. Count Primes

python

class Solution:
    def countPrimes(self, n: int) -> int:
        # scanning method 1
        if n <=1 :return 0
        nums = [1 for i in range(n)]
        nums[1],nums[0] = 0,0
        import math
        for i in range(2, int(math.sqrt(n)) +1):
            multiple = 2
            while(i * multiple < n):
                nums[i*multiple] =0
                multiple += 1
        return sum(nums)

class Solution2:
    def countPrimes(self, n: int) -> int:
        # scanning method 2
        # if current number isn't prime , it's not necessary to calc number multiply by it because current can be format by two smaller number
        if n <=2:
            return 0
        nums = [True]*n
        for i in range(2, int(n**0.5)+1):
            if nums[i]:
                count =2
                while(count * i < n):
                    nums[count * i] =False
                    count +=1
        return sum(nums)

class Solution3:
    def countPrimes(self, n: int) -> int:
        # scanning method 3
        # pythonic
        if n <=2 :return 0
        nums = [True] * n
        for i in range(2, int(n**.5)+1):
            if nums[i]:
                nums[i+i:n:i] = [False]*len(nums[i+i:n:i])
        return sum(nums) -2

Java

package Easy.HashTable;

public class CountPrimes {
    class Solution1 {
        // normal method, judge each number whether prime or not
        public int countPrimes(int n) {
            int result = 0;
            for (int i=1; i< n; i++){
                if (isPrime(i)) result+=1;
            }
            return result;
        }

        public boolean isPrime(int n){
            if (n <2) return false;
            if (n==2) return true;
            for(int i=2; i<= (int)(Math.sqrt(n)+1); i++){
                if (n % i ==0) return false;
            }
            return true;
        }
    }


   static class Solution2 {
        public int countPrimes(int n) {
            if (n <=1) return 0;
            boolean[] array = new boolean[n];
            for (int i =0; i < array.length; i++){
                if (i <= 1) array[i] = false;
                else array[i] = true;
            }
            for(int i=2; i<= (int)(Math.sqrt(n)+1); i++){
                int multile = 2;
                while(multile * i < n){
                    array[multile * i] = false;
                    multile +=1;
                }
            }
            int result = 0;
            for (boolean a: array){
                if (a) result += 1;
            }
            return result;
        }
    }


    static class Solution3 {
        public int countPrimes(int n) {
            if (n < 2) return 0;
            boolean[] array = new boolean[n];
            for (int i =1; i< array.length; i++){
                if (i <= 1) array[i] = false;
                else array[i] = true;
            }

            for (int i=2; i < (int)(Math.sqrt(n)+1); i++){
                if (array[i]){
                    int count =2;
                    while(count * i < n){
                        array[count * i] = false;
                        count += 1;
                    }
                }
            }
            int result = 0;
            for (boolean b : array){
                if (b)  result += 1;
            }
            return result;
        }
    }
}