我正在学习Python使用LeetCode的问题,遇到了计数素数的问题。 我已经创建了一个解决方案,但是,该程序在提交时返回“超过时间限制”。 我不知道为什么会这样。 为什么会发生这种情况?我如何改进我的解决方案以提高时间效率
简介: 计算小于非负数n的素数
例如:
输入:10 产出:4 说明:有4个素数小于10,它们是2,3,5,7
我的解决方案:
class Solution:
def isPrime(self,n: int) -> int:
isPrime = False
count = 0
for i in range (1,n+1): # Iterates through integers (acting as divisors) from 1 to n
if n % i == 0: # aka if n is divisible by i
count = count + 1
if count == 2: # if n only divisible by itself and 1
isPrime = True
return isPrime
def countPrimes(self,n):
totalPrimes = 0
for i in range(1,n): # runs from 1 to n-1
answer = self.isPrime(i)
if answer == True:
totalPrimes = totalPrimes + 1
return totalPrimes
在一定范围内计算素数的方法有很多种(但对于大数来说效率很低,而且很耗时)。你似乎有正确的想法,我们首先需要一个函数,正确地确定n是否为素数(一些像Fermat和Miller-Rabin这样快速的素数测试会给出误报)。试驾是最容易实施的(但只适用于少数人)。对于每个输入n,我们将检查是否存在基本p<;除以n的sqrt(n)。如果是,n是复合的,否则,n是素数。以下是我的解决方案:
我们还没有定义count_素数,因此输入超过1000将导致错误。这是素数计数函数(实际上,它返回小于或等于n的素数):
把二和二放在一起,我们可以用类似2000的东西调用count_primes函数:
返回的素数应小于2000:
要查看有多少,请致电
在这个范围内有303个素数
相关问题 更多 >
编程相关推荐