想象一下，你面前有一堆杂乱无章的数据，你需要从中找到特定的信息，或者按照一定的规则对这些数据进行排序。又或者，你要为一个物流公司规划最佳的配送路线，以降低成本和提高效率。这些问题看似复杂，但都可以通过特定的算法来解决。算法就像是一把神奇的钥匙，为解决各种各样的问题提供了方法和途径。无论是在科学研究、商业运营还是日常生活中，算法都发挥着不可或缺的作用。
原型—源码
原型
import math
import time
def is_prime(n):
for i in range(2, n):
if n % i == 0:
return False
return True
def prime_pq(n):
start = time.time()
for p in range(1, n):
for q in range(1, n):
# 如果找到因子且均为质数，则退出循环
if is_prime(p) and is_prime(q):
if p * q == n:
print(p, '*', q)
end = time.time()
print(end - start)
exit(0)
if __name__ == '__main__':
# 9973 * 9973
prime_pq(99460729)
原型—源码解析
这段代码的目的是找出一个给定数字的两个质数因子。下面是对代码的详细分析：
-
导入模块:
-
math: 这个模块提供了数学函数，但在这个代码中并没有被使用。 -
time: 这个模块被用来测量程序的执行时间。
-
-
is_prime函数:
-
这个函数用于判断一个数是否为质数。
-
它从2开始，一直检查到n-1，看n是否能被这些数整除。如果能，则n不是质数，返回False；否则，返回True。
-
但这个函数可以优化。例如，只需要检查到sqrt(n)就可以了，因为如果n有一个大于sqrt(n)的因子，那么它必然还有一个小于或等于sqrt(n)的因子。
-
-
prime_pq函数:
-
这个函数用于找出一个数的两个质数因子。
-
它从1开始，遍历到n-1，对于每个数p，再遍历从1到n-1的每个数q。
-
如果p和q都是质数，并且它们的乘积等于n，那么就找到了两个质数因子，打印出来并结束程序。
-
这个函数的时间复杂度是O(n^2)，因为它有两个嵌套的循环。对于大的n，这可能会非常慢。
-
-
主程序:
-
在主程序中，调用了prime_pq函数，传入的参数是99460729。
-
一次优化—源码
任何一个数只需要找其小于开根号的整数即可
import math
import time
def is_prime(n):
loop = int(math.sqrt(n)) + 1
for i in range(2, loop):
if n % i == 0:
return False
return True
def prime_pq(n):
start = time.time()
for p in range(1, n):
for q in range(1, n):
# 如果找到因子且均为质数，则退出循环
if is_prime(p) and is_prime(q):
if p * q == n:
print(p, '*', q)
end = time.time()
print(end - start)
exit(0)
if __name__ == '__main__':
# 9973 * 9973
prime_pq(99460729)
一次优化—源码解析
这段代码的目的是找出一个给定数字的两个质数因子。下面是对代码的详细分析：
-
导入模块:
-
math: 这个模块提供了数学函数，但在这个代码中并没有被使用。 -
time: 这个模块被用来测量程序的执行时间。
-
-
is_prime函数:
-
这个函数用于判断一个数是否为质数。
-
它从2开始，一直检查到n-1，看n是否能被这些数整除。如果能，则n不是质数，返回False；否则，返回True。
-
但这个函数可以优化。例如，只需要检查到sqrt(n)就可以了，因为如果n有一个大于sqrt(n)的因子，那么它必然还有一个小于或等于sqrt(n)的因子。
-
-
prime_pq函数:
-
这个函数用于找出一个数的两个质数因子。
-
它从1开始，遍历到n-1，对于每个数p，再遍历从1到n-1的每个数q。
-
如果p和q都是质数，并且它们的乘积等于n，那么就找到了两个质数因子，打印出来并结束程序。
-
这个函数的时间复杂度是O(n^2)，因为它有两个嵌套的循环。对于大的n，这可能会非常慢。
-
-
主程序:
-
在主程序中，调用了prime_pq函数，传入的参数是99460729。
-
二次优化—源码
跳过小于2的数
import math
import time
def is_prime(n):
if n < 2:
return False
loop = int(math.sqrt(n)) + 1
for i in range(2, loop):
if n % i == 0:
return False
return True
def prime_pq(n):
start = time.time()
for p in range(1, n):
for q in range(1, n):
# 如果找到因子且均为质数，则退出循环
if is_prime(p) and is_prime(q):
if p * q == n:
print(p, '*', q)
end = time.time()
print(end - start)
exit(0)
if __name__ == '__main__':
# 9973 * 9973
prime_pq(99460729)
二次优化—源码解析
这段代码的目的是找出一个给定数字的两个质数因子。下面是对代码的详细分析：
-
导入模块:
-
math: 这个模块提供了数学函数，但在这个代码中并没有被使用。 -
time: 这个模块被用来测量程序的执行时间。
-
-
is_prime函数:
-
这个函数用于判断一个数是否为质数。
-
它从2开始，一直检查到n-1，看n是否能被这些数整除。如果能，则n不是质数，返回False；否则，返回True。
-
但这个函数可以优化。例如，只需要检查到sqrt(n)就可以了，因为如果n有一个大于sqrt(n)的因子，那么它必然还有一个小于或等于sqrt(n)的因子。
-
-
prime_pq函数:
-
这个函数用于找出一个数的两个质数因子。
-
它从1开始，遍历到n-1，对于每个数p，再遍历从1到n-1的每个数q。
-
如果p和q都是质数，并且它们的乘积等于n，那么就找到了两个质数因子，打印出来并结束程序。
-
这个函数的时间复杂度是O(n^2)，因为它有两个嵌套的循环。对于大的n，这可能会非常慢。
-
-
主程序:
-
在主程序中，调用了prime_pq函数，传入的参数是99460729。
-
三次优化—源码
在检查大于2的数时，只检查奇数
import math
import time
def is_prime(n):
if n < 2:
return False
if n == 2:
return True
if n % 2 == 0:
return False
loop = int(math.sqrt(n)) + 1
for i in range(3, loop, 2):
if n % i == 0:
return False
return True
def prime_pq(n):
start = time.time()
for p in range(1, n):
for q in range(1, n):
# 如果找到因子且均为质数，则退出循环
if is_prime(p) and is_prime(q):
if p * q == n:
print(p, '*', q)
end = time.time()
print(end - start)
exit(0)
if __name__ == '__main__':
# 9973 * 9973
prime_pq(99460729)
三次优化—源码解析
这段代码的目的是找出一个给定数字的两个质数因子。下面是对代码的详细分析：
-
导入模块:
-
math: 这个模块提供了数学函数，但在这个代码中并没有被使用。 -
time: 这个模块被用来测量程序的执行时间。
-
-
is_prime函数:
-
这个函数用于判断一个数是否为质数。
-
首先排除小于2的数，因为它们不是质数。
-
对于2这个特殊的数，直接返回True。
-
对于偶数（除了2），直接返回False。
-
然后从3开始，只检查奇数（因为偶数已经被排除了），直到sqrt(n)。
-
如果在这个范围内找到一个能整除n的数，那么n就不是质数，返回False；否则，返回True。
-
-
prime_pq函数:
-
这个函数用于找出一个数的两个质数因子。
-
它从1开始，遍历到n-1，对于每个数p，再遍历从1到n-1的每个数q。
-
如果p和q都是质数，并且它们的乘积等于n，那么就找到了两个质数因子，打印出来并结束程序。
-
这个函数的时间复杂度是O(n^2)，因为它有两个嵌套的循环。对于大的n，这可能会非常慢。
-
-
主程序:
-
在主程序中，调用了prime_pq函数，传入的参数是99460729。
-
四次优化—源码
先算乘积
import math
import time
def is_prime(n):
for i in range(2, n):
if n % i == 0:
return False
return True
def prime_pq(n):
start = time.time()
for p in range(1, n):
for q in range(1, n):
if p * q == n:
if is_prime(p) and is_prime(q):
print(p, '*', q)
end = time.time()
print(end - start)
exit(0)
if __name__ == '__main__':
# 9973 * 9973
prime_pq(99460729)
四次优化—源码解析
这段代码的目的是找出一个给定数字的两个质数因子。下面是对代码的详细分析：
-
导入模块:
-
math: 这个模块提供了数学函数，但在这个代码中并没有被使用。 -
time: 这个模块被用来测量程序的执行时间。
-
-
is_prime函数:
-
这个函数用于判断一个数是否为质数。
-
它从2开始，一直检查到n-1，看n是否能被这些数整除。如果能，则n不是质数，返回False；否则，返回True。
-
但这个函数可以优化。例如，只需要检查到sqrt(n)就可以了，因为如果n有一个大于sqrt(n)的因子，那么它必然还有一个小于或等于sqrt(n)的因子。
-
-
prime_pq函数:
-
这个函数用于找出一个数的两个质数因子。
-
它从1开始，遍历到n-1，对于每个数p，再遍历从1到n-1的每个数q。
-
如果p和q都是质数，并且它们的乘积等于n，那么就找到了两个质数因子，打印出来并结束程序。
-
这个函数的时间复杂度是O(n^2)，因为它有两个嵌套的循环。对于大的n，这可能会非常慢。
-
-
主程序:
-
在主程序中，调用了prime_pq函数，传入的参数是99460729。
-
五次优化—源码
任何一个数只需要找其小于开根号的整数即可 先算乘积
import math
import time
def is_prime(n):
loop = int(math.sqrt(n)) + 1
for i in range(2, loop):
if n % i == 0:
return False
return True
def prime_pq(n):
start = time.time()
for p in range(1, n):
for q in range(1, n):
if p * q == n:
if is_prime(p) and is_prime(q):
print(p, '*', q)
end = time.time()
print(end - start)
exit(0)
if __name__ == '__main__':
# 9973 * 9973
prime_pq(99460729)
五次优化—源码解析
这段代码的目的是找出一个给定数字的两个质数因子。下面是对代码的详细分析：
-
导入模块:
-
math: 这个模块提供了数学函数，但在这个代码中并没有被使用。 -
time: 这个模块被用来测量程序的执行时间。
-
-
is_prime函数:
-
这个函数用于判断一个数是否为质数。
-
它从2开始，一直检查到n-1，看n是否能被这些数整除。如果能，则n不是质数，返回False；否则，返回True。
-
但这个函数可以优化。例如，只需要检查到sqrt(n)就可以了，因为如果n有一个大于sqrt(n)的因子，那么它必然还有一个小于或等于sqrt(n)的因子。
-
-
prime_pq函数:
-
这个函数用于找出一个数的两个质数因子。
-
它从1开始，遍历到n-1，对于每个数p，再遍历从1到n-1的每个数q。
-
如果p和q都是质数，并且它们的乘积等于n，那么就找到了两个质数因子，打印出来并结束程序。
-
这个函数的时间复杂度是O(n^2)，因为它有两个嵌套的循环。对于大的n，这可能会非常慢。
-
-
主程序:
-
在主程序中，调用了prime_pq函数，传入的参数是99460729。
-
六次优化—源码
跳过小于2的数 先算乘积
import math
import time
def is_prime(n):
if n < 2:
return False
loop = int(math.sqrt(n)) + 1
for i in range(2, loop):
if n % i == 0:
return False
return True
def prime_pq(n):
start = time.time()
for p in range(1, n):
for q in range(1, n):
if p * q == n:
if is_prime(p) and is_prime(q):
print(p, '*', q)
end = time.time()
print(end - start)
exit(0)
if __name__ == '__main__':
# 9973 * 9973
prime_pq(99460729)
六次优化—源码解析
这段代码的目的是找出一个给定数字的两个质数因子。下面是对代码的详细分析：
-
导入模块:
-
math: 这个模块提供了数学函数，但在这个代码中并没有被使用。 -
time: 这个模块被用来测量程序的执行时间。
-
-
is_prime函数:
-
这个函数用于判断一个数是否为质数。
-
首先排除小于2的数，因为它们不是质数。
-
对于2这个特殊的数，直接返回True。
-
对于偶数（除了2），直接返回False。
-
然后从3开始，只检查奇数（因为偶数已经被排除了），直到sqrt(n)。
-
如果在这个范围内找到一个能整除n的数，那么n就不是质数，返回False；否则，返回True。
-
-
prime_pq函数:
-
这个函数用于找出一个数的两个质数因子。
-
它从1开始，遍历到n-1，对于每个数p，再遍历从1到n-1的每个数q。
-
如果p和q都是质数，并且它们的乘积等于n，那么就找到了两个质数因子，打印出来并结束程序。
-
这个函数的时间复杂度是O(n^2)，因为它有两个嵌套的循环。对于大的n，这可能会非常慢。
-
-
主程序:
-
在主程序中，调用了prime_pq函数，传入的参数是99460729。
-
七次优化—源码
在检查大于2的数时，只检查奇数 先算乘积
import math
import time
def is_prime(n):
if n < 2:
return False
if n == 2:
return True
if n % 2 == 0:
return False
loop = int(math.sqrt(n)) + 1
for i in range(3, loop, 2):
if n % i == 0:
return False
return True
def prime_pq(n):
start = time.time()
for p in range(1, n):
for q in range(1, n):
if p * q == n:
if is_prime(p) and is_prime(q):
print(p, '*', q)
end = time.time()
print(end - start)
exit(0)
if __name__ == '__main__':
# 9973 * 9973
prime_pq(99460729)
七次优化—源码解析
这段代码的目的是找出一个给定数字的两个质数因子。下面是对代码的详细分析：
-
导入模块:
-
math: 这个模块提供了数学函数，但在这个代码中并没有被使用。 -
time: 这个模块被用来测量程序的执行时间。
-
-
is_prime函数:
-
这个函数用于判断一个数是否为质数。
-
首先排除小于2的数，因为它们不是质数。
-
对于2这个特殊的数，直接返回True。
-
对于偶数（除了2），直接返回False。
-
然后从3开始，只检查奇数（因为偶数已经被排除了），直到sqrt(n)。
-
如果在这个范围内找到一个能整除n的数，那么n就不是质数，返回False；否则，返回True。
-
-
prime_pq函数:
-
这个函数用于找出一个数的两个质数因子。
-
它从1开始，遍历到n-1，对于每个数p，再遍历从1到n-1的每个数q。
-
如果p和q都是质数，并且它们的乘积等于n，那么就找到了两个质数因子，打印出来并结束程序。
-
这个函数的时间复杂度是O(n^2)，因为它有两个嵌套的循环。对于大的n，这可能会非常慢。
-
-
主程序:
-
在主程序中，调用了prime_pq函数，传入的参数是99460729。
-
八次次优化—源码
p、q循环减半
import math
import time
def is_prime(n):
for i in range(2, n):
if n % i == 0:
return False
return True
def prime_pq(n):
start = time.time()
for p in range(1, n // 2 + 1):
for q in range(1, n // 2 + 1):
if p * q == n:
if is_prime(p) and is_prime(q):
print(p, '*', q)
end = time.time()
print(end - start)
exit(0)
if __name__ == '__main__':
# 9973 * 9973
prime_pq(99460729)
八次优化—源码解析
这段代码的目的是找出一个给定数字的两个质数因子。下面是对代码的详细分析：
-
导入模块:
-
math: 这个模块提供了数学函数，但在这个代码中并没有被使用。 -
time: 这个模块被用来测量程序的执行时间。
-
-
is_prime函数:
-
这个函数用于判断一个数是否为质数。
-
它从2开始，一直检查到n-1，看n是否能被这些数整除。如果能，则n不是质数，返回False；否则，返回True。
-
但这个函数可以优化。例如，只需要检查到sqrt(n)就可以了，因为如果n有一个大于sqrt(n)的因子，那么它必然还有一个小于或等于sqrt(n)的因子。
-
-
prime_pq函数:
-
这个函数用于找出一个数的两个质数因子。
-
它从1开始，遍历到n//2 + 1，对于每个数p，再遍历从1到n//2 + 1的每个数q。
-
如果p和q都是质数，并且它们的乘积等于n，那么就找到了两个质数因子，打印出来并结束程序。
-
这个函数的时间复杂度是O(n^2)，因为它有两个嵌套的循环。对于大的n，这可能会非常慢。
-
-
主程序:
-
在主程序中，调用了prime_pq函数，传入的参数是99460729。
-
九次优化—源码
任何一个数只需要找其小于开根号的整数即可 p、q循环减半
import math
import time
def is_prime(n):
loop = int(math.sqrt(n)) + 1
for i in range(2, loop):
if n % i == 0:
return False
return True
def prime_pq(n):
start = time.time()
for p in range(1, n // 2 + 1):
for q in range(1, n // 2 + 1):
if p * q == n:
if is_prime(p) and is_prime(q):
print(p, '*', q)
end = time.time()
print(end - start)
exit(0)
if __name__ == '__main__':
# 9973 * 9973
prime_pq(99460729)
九次优化—源码解析
这段代码的目的是找出一个给定数字的两个质数因子。下面是对代码的详细分析：
-
导入模块:
-
math: 这个模块提供了数学函数，但在这个代码中并没有被使用。 -
time: 这个模块被用来测量程序的执行时间。
-
-
is_prime函数:
-
这个函数用于判断一个数是否为质数。
-
它从2开始，一直检查到n-1，看n是否能被这些数整除。如果能，则n不是质数，返回False；否则，返回True。
-
但这个函数可以优化。例如，只需要检查到sqrt(n)就可以了，因为如果n有一个大于sqrt(n)的因子，那么它必然还有一个小于或等于sqrt(n)的因子。
-
-
prime_pq函数:
-
这个函数用于找出一个数的两个质数因子。
-
它从1开始，遍历到n//2 + 1，对于每个数p，再遍历从1到n//2 + 1的每个数q。
-
如果p和q都是质数，并且它们的乘积等于n，那么就找到了两个质数因子，打印出来并结束程序。
-
这个函数的时间复杂度是O(n^2)，因为它有两个嵌套的循环。对于大的n，这可能会非常慢。
-
-
主程序:
-
在主程序中，调用了prime_pq函数，传入的参数是99460729。
-
十次优化—源码
跳过小于2的数 p、q循环减半
import math
import time
def is_prime(n):
if n < 2:
return False
loop = int(math.sqrt(n)) + 1
for i in range(2, loop):
if n % i == 0:
return False
return True
def prime_pq(n):
start = time.time()
for p in range(1, n // 2 + 1):
for q in range(1, n // 2 + 1):
if p * q == n:
if is_prime(p) and is_prime(q):
print(p, '*', q)
end = time.time()
print(end - start)
exit(0)
if __name__ == '__main__':
# 9973 * 9973
prime_pq(99460729)
十次优化—源码解析
这段代码的目的是找出一个给定数字的两个质数因子。下面是对代码的详细分析：
-
导入模块:
-
math: 这个模块提供了数学函数，但在这个代码中并没有被使用。 -
time: 这个模块被用来测量程序的执行时间。
-
-
is_prime函数:
-
这个函数用于判断一个数是否为质数。
-
首先排除小于2的数，因为它们不是质数。
-
对于2这个特殊的数，直接返回True。
-
对于偶数（除了2），直接返回False。
-
然后从3开始，只检查奇数（因为偶数已经被排除了），直到sqrt(n)。
-
如果在这个范围内找到一个能整除n的数，那么n就不是质数，返回False；否则，返回True。
-
-
prime_pq函数:
-
这个函数用于找出一个数的两个质数因子。
-
它从1开始，遍历到n//2 + 1，对于每个数p，再遍历从1到n//2 + 1的每个数q。
-
如果p和q都是质数，并且它们的乘积等于n，那么就找到了两个质数因子，打印出来并结束程序。
-
这个函数的时间复杂度是O(n^2)，因为它有两个嵌套的循环。对于大的n，这可能会非常慢。
-
-
主程序:
-
在主程序中，调用了prime_pq02函数，传入的参数是99460729。
-
优化建议:
-
优化
is_prime函数，只需要检查到sqrt(n)就可以了。 -
对于
prime_pq02函数，可以考虑使用更高效的算法，如试除法结合埃拉托斯特尼筛法来找出质数因子。 -
可以添加更多的错误检查和边界条件处理，例如检查输入的n是否为正整数。
下面是优化后的代码：
import math
import time
def is_prime(n):
if n <= 1:
return False
if n == 2:
return True
if n % 2 == 0:
return False
loop = int(math.sqrt(n)) + 1
for i in range(3, loop, 2):
if n % i == 0:
return False
return True
def prime_pq(n):
start = time.time()
for p in range(2, int(math.sqrt(n)) + 1):
if is_prime(p) and n % p == 0:
q = n // p
if is_prime(q):
print(p, '*', q)
end = time.time()
print(end - start)
return
print("No prime factors found")
if __name__ == '__main__':
prime_pq02(99460729)
这个优化后的代码应该会更快地找到99460729的两个质数因子。
十一次优化—源码
在检查大于2的数时，只检查奇数 p、q循环减半
import math
import time
def is_prime(n):
if n < 2:
return False
if n == 2:
return True
if n % 2 == 0:
return False
loop = int(math.sqrt(n)) + 1
for i in range(3, loop, 2):
if n % i == 0:
return False
return True
def prime_pq(n):
start = time.time()
for p in range(1, n // 2 + 1):
for q in range(1, n // 2 + 1):
if p * q == n:
if is_prime(p) and is_prime(q):
print(p, '*', q)
end = time.time()
print(end - start)
exit(0)
if __name__ == '__main__':
# 9973 * 9973
prime_pq(99460729)
十一次优化—源码解析
这段代码的目的是找出一个给定数字的两个质数因子。下面是对代码的详细分析：
-
导入模块:
-
math: 这个模块提供了数学函数，但在这个代码中并没有被使用。 -
time: 这个模块被用来测量程序的执行时间。
-
-
is_prime函数:
-
这个函数用于判断一个数是否为质数。
-
首先排除小于2的数，因为它们不是质数。
-
对于2这个特殊的数，直接返回True。
-
对于偶数（除了2），直接返回False。
-
然后从3开始，只检查奇数（因为偶数已经被排除了），直到sqrt(n)。
-
如果在这个范围内找到一个能整除n的数，那么n就不是质数，返回False；否则，返回True。
-
-
prime_pq函数:
-
这个函数用于找出一个数的两个质数因子。
-
它从1开始，遍历到n//2 + 1，对于每个数p，再遍历从1到n//2 + 1的每个数q。
-
如果p和q都是质数，并且它们的乘积等于n，那么就找到了两个质数因子，打印出来并结束程序。
-
这个函数的时间复杂度是O(n^2)，因为它有两个嵌套的循环。对于大的n，这可能会非常慢。
-
-
主程序:
-
在主程序中，调用了prime_pq函数，传入的参数是99460729。
-
十二次优化—源码
减少p、q循环时间，并对判断p、q为循环优化依次调用
import math
import time
def is_prime(n):
for i in range(2, n):
if n % i == 0:
return False
return True
def prime_pq(n):
start = time.time()
for p in range(2, int(math.sqrt(n)) + 1):
if n % p == 0:
q = n // p
if is_prime(p) and is_prime(q):
print(p, '*', q)
end = time.time()
print(end - start)
exit(0)
if __name__ == '__main__':
# 9973 * 9973
prime_pq(99460729)
十二次优化—源码解析
这段代码的目的是找出一个给定数字的两个质数因子。下面是对代码的详细分析：
-
导入模块:
-
math: 这个模块提供了数学函数，但在这个代码中并没有被使用。 -
time: 这个模块被用来测量程序的执行时间。
-
-
is_prime函数:
-
这个函数用于判断一个数是否为质数。
-
它从2开始，一直检查到n-1，看n是否能被这些数整除。如果能，则n不是质数，返回False；否则，返回True。
-
但这个函数可以优化。例如，只需要检查到sqrt(n)就可以了，因为如果n有一个大于sqrt(n)的因子，那么它必然还有一个小于或等于sqrt(n)的因子。
-
-
prime_pq函数:
-
这个函数用于找出一个数的两个质数因子。
-
它从2开始，遍历到n的平方根加1，对于每个数p，如果n能被p整除，那么计算q = n // p。
-
然后检查p和q是否都是质数，如果是，则打印出这两个质数因子，并结束程序。
-
这个函数的时间复杂度是O(n^2)，因为它有两个嵌套的循环。对于大的n，这可能会非常慢。
-
-
主程序:
-
在主程序中，调用了prime_pq函数，传入的参数是99460729。
-
十三次优化—源码
任何一个数只需要找其小于开根号的整数即可 减少p、q循环时间，并对判断p、q为循环优化依次调用
import math
import time
def is_prime(n):
loop = int(math.sqrt(n)) + 1
for i in range(2, loop):
if n % i == 0:
return False
return True
def prime_pq(n):
start = time.time()
for p in range(2, int(math.sqrt(n)) + 1):
if n % p == 0:
q = n // p
if is_prime(p) and is_prime(q):
print(p, '*', q)
end = time.time()
print(end - start)
exit(0)
if __name__ == '__main__':
# 9973 * 9973
prime_pq(99460729)
十三次优化—源码解析
这段代码的目的是找出一个给定数字的两个质数因子。下面是对代码的详细分析：
-
导入模块:
-
math: 这个模块提供了数学函数，但在这个代码中并没有被使用。 -
time: 这个模块被用来测量程序的执行时间。
-
-
is_prime函数:
-
这个函数用于判断一个数是否为质数。
-
它从2开始，一直检查到n-1，看n是否能被这些数整除。如果能，则n不是质数，返回False；否则，返回True。
-
但这个函数可以优化。例如，只需要检查到sqrt(n)就可以了，因为如果n有一个大于sqrt(n)的因子，那么它必然还有一个小于或等于sqrt(n)的因子。
-
-
prime_pq函数:
-
这个函数用于找出一个数的两个质数因子。
-
它从2开始，遍历到n的平方根加1，对于每个数p，如果n能被p整除，那么计算q = n // p。
-
然后检查p和q是否都是质数，如果是，则打印出这两个质数因子，并结束程序。
-
这个函数的时间复杂度是O(n^2)，因为它有两个嵌套的循环。对于大的n，这可能会非常慢。
-
-
主程序:
-
在主程序中，调用了prime_pq函数，传入的参数是99460729。
-
十四次优化—源码
跳过小于2的数 减少p、q循环时间，并对判断p、q为循环优化依次调用
import math
import time
def is_prime(n):
if n < 2:
return False
loop = int(math.sqrt(n)) + 1
for i in range(2, loop):
if n % i == 0:
return False
return True
def prime_pq(n):
start = time.time()
for p in range(2, int(math.sqrt(n)) + 1):
if n % p == 0:
q = n // p
if is_prime(p) and is_prime(q):
print(p, '*', q)
end = time.time()
print(end - start)
exit(0)
if __name__ == '__main__':
# 9973 * 9973
prime_pq(99460729)
十四次优化—源码解析
这段代码的目的是找出一个给定数字的两个质数因子。下面是对代码的详细分析：
-
导入模块:
-
math: 这个模块提供了数学函数，但在这个代码中并没有被使用。 -
time: 这个模块被用来测量程序的执行时间。
-
-
is_prime函数:
-
这个函数用于判断一个数是否为质数。
-
首先排除小于2的数，因为它们不是质数。
-
对于2这个特殊的数，直接返回True。
-
对于偶数（除了2），直接返回False。
-
然后从3开始，只检查奇数（因为偶数已经被排除了），直到sqrt(n)。
-
如果在这个范围内找到一个能整除n的数，那么n就不是质数，返回False；否则，返回True。
-
-
prime_pq函数:
-
这个函数用于找出一个数的两个质数因子。
-
它从2开始，遍历到n的平方根加1，对于每个数p，如果n能被p整除，那么计算q = n // p。
-
然后检查p和q是否都是质数，如果是，则打印出这两个质数因子，并结束程序。
-
这个函数的时间复杂度是O(n^2)，因为它有两个嵌套的循环。对于大的n，这可能会非常慢。
-
-
主程序:
-
在主程序中，调用了prime_pq函数，传入的参数是99460729。
-
最终优化—源码
在检查大于2的数时，只检查奇数 减少p、q循环时间，并对判断p、q为循环优化依次调用
import math
import time
def is_prime(n):
if n < 2:
return False
if n == 2:
return True
if n % 2 == 0:
return False
loop = int(math.sqrt(n)) + 1
for i in range(3, loop, 2):
if n % i == 0:
return False
return True
def prime_pq(n):
start = time.time()
for p in range(2, int(math.sqrt(n)) + 1):
if n % p == 0:
q = n // p
if is_prime(p) and is_prime(q):
print(p, '*', q)
end = time.time()
print(end - start)
exit(0)
if __name__ == '__main__':
# 9973 * 9973
prime_pq(99460729)
最终优化—源码解析
这段代码的目的是找出一个给定数字的两个质数因子。下面是对代码的详细分析：
-
导入模块:
-
math: 这个模块提供了数学函数，但在这个代码中并没有被使用。 -
time: 这个模块被用来测量程序的执行时间。
-
-
is_prime函数:
-
这个函数用于判断一个数是否为质数。
-
首先排除小于2的数，因为它们不是质数。
-
对于2这个特殊的数，直接返回True。
-
对于偶数（除了2），直接返回False。
-
然后从3开始，只检查奇数（因为偶数已经被排除了），直到sqrt(n)。
-
如果在这个范围内找到一个能整除n的数，那么n就不是质数，返回False；否则，返回True。
-
-
prime_pq函数:
-
这个函数用于找出一个数的两个质数因子。
-
它从2开始，遍历到n的平方根加1，对于每个数p，如果n能被p整除，那么计算q = n // p。
-
然后检查p和q是否都是质数，如果是，则打印出这两个质数因子，并结束程序。
-
这个函数的时间复杂度是O(n^2)，因为它有两个嵌套的循环。对于大的n，这可能会非常慢。
-
-
主程序:
-
在主程序中，调用了prime_pq函数，传入的参数是99460729。
-
高阶优化
思路：
1、优化is_prime函数，只需要检查到sqrt(n)就可以了。
2、prime_pq函数，可以考虑使用更高效的算法，如试除法结合埃拉托斯特尼筛法/Pollard's rho算法来找出质数因子。
3、并行化处理在多核处理器上运行，可以将筛选质数或者试除的过程进行并行化，进一步提高效率。
4、添加更多的错误检查和边界条件处理，例如检查输入的n是否为正整数。
以后有时间再来演示高阶算法。
