我已经编写了程序来查找素数,尽可能多地使用技术来查找素数。然而,在网上搜索时(在 GeekforGeek 上),我发现了一个与我的有点相似的(算法思想相同),但产生相同结果的速度要快得多。我想知道这两者有什么区别
我们都减少了测试 1) 只检查奇数。 2) 只有奇数才有除数 3) 只允许除数达到那个数的平方根
#my code
import time
import math
start = time.time()
upperlimit = 1000000
counter = 1
number = 3
while number<upperlimit: #loop to check number
shittyvalue = 0
division = 3
while math.sqrt(number) >= division: # conditional loop
if number % division == 0:
shittyvalue = 1 #for giving the annoucement on whether this number is a prime
break
division = division + 2
if shittyvalue == 0:
counter = counter + 1
number = number + 2
print ("There are ",counter, " prime numbers")
end = time.time()
print ("Found in ",end-start, " seconds")
#GeekforGeek code's
# Python Program to find prime numbers in a range
import math
import time
def is_prime(n):
if n <= 1:
return False
if n == 2:
return True
if n > 2 and n % 2 == 0:
return False
max_div = math.floor(math.sqrt(n))
for i in range(3, 1 + max_div, 2):
if n % i == 0:
return False
return True
# Driver function
t0 = time.time()
c = 0 #for counting
for n in range(1,1000000):
x = is_prime(n)
c += x
print("Total prime numbers in range :", c)
t1 = time.time()
print("Time required :", t1 - t0)
显示的结果:
我的:有78498个质数 在 17.29092025756836 秒内找到
GeekforGeek:范围内的素数总数:78498 所需时间:3.9572863578796387
最佳答案
您可以将 Math.sqrt(number) 从 while 循环中取出。当n很大时,这是一个繁重的操作。
For 循环比 Python 中的 while 循环更快 Why is looping over range() in Python faster than using a while loop?
关于python - 我在 Python 中有 2 个代码用于查找素数。为什么在这两个代码中,一个产生结果的速度比另一个快得多,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57958039/