质数的计数

# -*- coding: utf-8 -*-


import math


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param n int整型
# @return int整型
#
class Solution1:
    """
    题目：
        https://www.nowcoder.com/practice/190167d1990442da9adb133980259a27?tpId=196&tqId=40499&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    算法（法1）：
        遍历1 ~ n，对于每一个num进行判断，统计质数的总数
    复杂度：
        时间复杂度：O(n * sqrt(n))
        空间复杂度：O(1)
    """

    def primesCount(self, n):
        # write code here
        def isPrimes(x):
            for i in range(2, int(math.sqrt(x)) + 1):
                if x % i == 0:
                    return False
            return True

        count = 0

        for i in range(2, n):
            if isPrimes(i):
                count += 1

        return count


class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/190167d1990442da9adb133980259a27?tpId=196&tqId=40499&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    算法（法2）：
        基于一个事实：如果x是质数，那么x的整数倍(除自身外，2x, 3x,...,nx)一定是合数。
        我们使用primes记录0 ~ n数是否为质数，primes[i] = 1表示质数，primes[i] = 0表示合数。
        遇到质数，count += 1，我们就将该质数的倍数（除自身外）全部更新为合数。
    复杂度：
        时间复杂度：O(nlogn)
        空间复杂度：O(n)
    """

    def primesCount(self, n):
        # write code here
        primes, count = [1] * (n + 1), 0
        for i in range(2, n):
            if primes[i]:
                count += 1
                j = i * i
                while j < n:
                    primes[j] = 0
                    j += i
        return count


if __name__ == "__main__":
    sol = Solution()

    # n = 5

    # n = 10

    n = 94244

    res = sol.primesCount(n)

    print res

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型
     */
    public int primesCount (int n) {
      return  process(n-1);
    }
    public int process(int n) {
        if (n == 0) {
            return 0;
        }
        return process(n - 1) + (IsZ(n) == true ? 1 : 0);
    }
    
    public boolean IsZ(int date) {
        if (date <= 1 || date > 2 && date % 2 == 0) {
            return false;
        } else if (date == 2) {
            return true;
        }
        for (int i = 3; i <= Math.sqrt(date); i += 2) {
            if (date % i == 0) {
                return false;
            }
        }
        return true;
    }
}

class Solution {
public:
    
    int primesCount(int n) {
        vector<bool> prim(n,false);
        int cnt=0;
        for(int i=2;i<n;i++){
            if(!prim[i]) cnt++;
            for(int j=1;j*i<n;j++){
                prim[i*j]=true;
            }
        }
        return cnt;
    }
};