网站icp备案是什么,做特卖的购物网站,游戏外包公司是干嘛的,制作小程序的步骤想象一下#xff0c;你面前有一堆杂乱无章的数据#xff0c;你需要从中找到特定的信息#xff0c;或者按照一定的规则对这些数据进行排序。又或者#xff0c;你要为一个物流公司规划最佳的配送路线#xff0c;以降低成本和提高效率。这些问题看似复杂#xff0c;但都可以…想象一下你面前有一堆杂乱无章的数据你需要从中找到特定的信息或者按照一定的规则对这些数据进行排序。又或者你要为一个物流公司规划最佳的配送路线以降低成本和提高效率。这些问题看似复杂但都可以通过特定的算法来解决。算法就像是一把神奇的钥匙为解决各种各样的问题提供了方法和途径。无论是在科学研究、商业运营还是日常生活中算法都发挥着不可或缺的作用。
原型—源码
原型
import math
import timedef is_prime(n):for i in range(2, n):if n % i 0:return Falsereturn Truedef 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 * 9973prime_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 timedef is_prime(n):loop int(math.sqrt(n)) 1for i in range(2, loop):if n % i 0:return Falsereturn Truedef 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 * 9973prime_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 timedef is_prime(n):if n 2:return Falseloop int(math.sqrt(n)) 1for i in range(2, loop):if n % i 0:return Falsereturn Truedef 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 * 9973prime_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 timedef is_prime(n):if n 2:return Falseif n 2:return Trueif n % 2 0:return Falseloop int(math.sqrt(n)) 1for i in range(3, loop, 2):if n % i 0:return Falsereturn Truedef 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 * 9973prime_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 timedef is_prime(n):for i in range(2, n):if n % i 0:return Falsereturn Truedef 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 * 9973prime_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 timedef is_prime(n):loop int(math.sqrt(n)) 1for i in range(2, loop):if n % i 0:return Falsereturn Truedef 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 * 9973prime_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 timedef is_prime(n):if n 2:return Falseloop int(math.sqrt(n)) 1for i in range(2, loop):if n % i 0:return Falsereturn Truedef 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 * 9973prime_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 timedef is_prime(n):if n 2:return Falseif n 2:return Trueif n % 2 0:return Falseloop int(math.sqrt(n)) 1for i in range(3, loop, 2):if n % i 0:return Falsereturn Truedef 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 * 9973prime_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 timedef is_prime(n):for i in range(2, n):if n % i 0:return Falsereturn Truedef 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 * 9973prime_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 timedef is_prime(n):loop int(math.sqrt(n)) 1for i in range(2, loop):if n % i 0:return Falsereturn Truedef 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 * 9973prime_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 timedef is_prime(n):if n 2:return Falseloop int(math.sqrt(n)) 1for i in range(2, loop):if n % i 0:return Falsereturn Truedef 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 * 9973prime_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 timedef is_prime(n):if n 1:return Falseif n 2:return Trueif n % 2 0:return Falseloop int(math.sqrt(n)) 1for i in range(3, loop, 2):if n % i 0:return Falsereturn Truedef 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 // pif is_prime(q):print(p, *, q)end time.time()print(end - start)returnprint(No prime factors found)if __name__ __main__:prime_pq02(99460729)这个优化后的代码应该会更快地找到99460729的两个质数因子。
十一次优化—源码
在检查大于2的数时只检查奇数 p、q循环减半
import math
import timedef is_prime(n):if n 2:return Falseif n 2:return Trueif n % 2 0:return Falseloop int(math.sqrt(n)) 1for i in range(3, loop, 2):if n % i 0:return Falsereturn Truedef 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 * 9973prime_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 timedef is_prime(n):for i in range(2, n):if n % i 0:return Falsereturn Truedef prime_pq(n):start time.time()for p in range(2, int(math.sqrt(n)) 1):if n % p 0:q n // pif is_prime(p) and is_prime(q):print(p, *, q)end time.time()print(end - start)exit(0)if __name__ __main__:# 9973 * 9973prime_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 timedef is_prime(n):loop int(math.sqrt(n)) 1for i in range(2, loop):if n % i 0:return Falsereturn Truedef prime_pq(n):start time.time()for p in range(2, int(math.sqrt(n)) 1):if n % p 0:q n // pif is_prime(p) and is_prime(q):print(p, *, q)end time.time()print(end - start)exit(0)if __name__ __main__:# 9973 * 9973prime_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 timedef is_prime(n):if n 2:return Falseloop int(math.sqrt(n)) 1for i in range(2, loop):if n % i 0:return Falsereturn Truedef prime_pq(n):start time.time()for p in range(2, int(math.sqrt(n)) 1):if n % p 0:q n // pif is_prime(p) and is_prime(q):print(p, *, q)end time.time()print(end - start)exit(0)if __name__ __main__:# 9973 * 9973prime_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 timedef is_prime(n):if n 2:return Falseif n 2:return Trueif n % 2 0:return Falseloop int(math.sqrt(n)) 1for i in range(3, loop, 2):if n % i 0:return Falsereturn Truedef prime_pq(n):start time.time()for p in range(2, int(math.sqrt(n)) 1):if n % p 0:q n // pif is_prime(p) and is_prime(q):print(p, *, q)end time.time()print(end - start)exit(0)if __name__ __main__:# 9973 * 9973prime_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函数可以考虑使用更高效的算法如试除法结合埃拉托斯特尼筛法/Pollards rho算法来找出质数因子。
3、并行化处理在多核处理器上运行可以将筛选质数或者试除的过程进行并行化进一步提高效率。
4、添加更多的错误检查和边界条件处理例如检查输入的n是否为正整数。以后有时间再来演示高阶算法。
