假设我们有一个极限n。我们必须计算2到n范围内的质数。因此,如果n = 10,则结果将为4。由于在10之前有四个素数,它们分别为2、3、5、7。
为了解决这个问题,我们将遵循这种方法-
计数= 0
取一个大小为n + 1的素数数组,并用False填充
对于i = 0到n
计数增加1
设j = 2
当j * i <n时
prime [i * j] =真
j = j + 1
如果prime [i] = false,则
返回计数
让我们看下面的实现以更好地理解-
class Solution(object): def countPrimes(self, n): """ :type n: int :rtype: int """ count = 0 primes = [False for i in range(n+1)] for i in range(2,n): if primes[i] == False: count+=1 j = 2 while j*i<n: primes[j*i] = True j+=1 return count ob1 = Solution() print(ob1.countPrimes(50)) print(ob1.countPrimes(10))
n = 50 n = 10
输出结果
15 4