给定一个正整数 n ,请你计算小于 n 的质数的数量。
质数是除了 1 和自己以外不含有任何因数的数。
数据范围:
# -*- 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