python - 我在 Python 中有 2 个代码用于查找素数。为什么在这两个代码中，一个产生结果的速度比另一个快得多

Question

我已经编写了程序来查找素数，尽可能多地使用技术来查找素数。然而，在网上搜索时(在 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

Answer 1

您可以将 Math.sqrt(number) 从 while 循环中取出。当n很大时，这是一个繁重的操作。

For 循环比 Python 中的 while 循环更快 Why is looping over range() in Python faster than using a while loop?