当前位置： 首页 > news >正文

《深度剖析算法优化：提升效率与精度的秘诀》

news 2025/6/22 21:23:35

想象一下，你面前有一堆杂乱无章的数据，你需要从中找到特定的信息，或者按照一定的规则对这些数据进行排序。又或者，你要为一个物流公司规划最佳的配送路线，以降低成本和提高效率。这些问题看似复杂，但都可以通过特定的算法来解决。算法就像是一把神奇的钥匙，为解决各种各样的问题提供了方法和途径。无论是在科学研究、商业运营还是日常生活中，算法都发挥着不可或缺的作用。

原型—源码

原型

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)

原型—源码解析

这段代码的目的是找出一个给定数字的两个质数因子。下面是对代码的详细分析：

  1. 导入模块:

    • math: 这个模块提供了数学函数，但在这个代码中并没有被使用。

    • time: 这个模块被用来测量程序的执行时间。

  2. is_prime函数:

    • 这个函数用于判断一个数是否为质数。

    • 它从2开始，一直检查到n-1，看n是否能被这些数整除。如果能，则n不是质数，返回False；否则，返回True。

    • 但这个函数可以优化。例如，只需要检查到sqrt(n)就可以了，因为如果n有一个大于sqrt(n)的因子，那么它必然还有一个小于或等于sqrt(n)的因子。

  3. prime_pq函数:

    • 这个函数用于找出一个数的两个质数因子。

    • 它从1开始，遍历到n-1，对于每个数p，再遍历从1到n-1的每个数q。

    • 如果p和q都是质数，并且它们的乘积等于n，那么就找到了两个质数因子，打印出来并结束程序。

    • 这个函数的时间复杂度是O(n^2)，因为它有两个嵌套的循环。对于大的n，这可能会非常慢。

  4. 主程序:

    • 在主程序中，调用了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)

一次优化—源码解析

这段代码的目的是找出一个给定数字的两个质数因子。下面是对代码的详细分析：

  1. 导入模块:

    • math: 这个模块提供了数学函数，但在这个代码中并没有被使用。

    • time: 这个模块被用来测量程序的执行时间。

  2. is_prime函数:

    • 这个函数用于判断一个数是否为质数。

    • 它从2开始，一直检查到n-1，看n是否能被这些数整除。如果能，则n不是质数，返回False；否则，返回True。

    • 但这个函数可以优化。例如，只需要检查到sqrt(n)就可以了，因为如果n有一个大于sqrt(n)的因子，那么它必然还有一个小于或等于sqrt(n)的因子。

  3. prime_pq函数:

    • 这个函数用于找出一个数的两个质数因子。

    • 它从1开始，遍历到n-1，对于每个数p，再遍历从1到n-1的每个数q。

    • 如果p和q都是质数，并且它们的乘积等于n，那么就找到了两个质数因子，打印出来并结束程序。

    • 这个函数的时间复杂度是O(n^2)，因为它有两个嵌套的循环。对于大的n，这可能会非常慢。

  4. 主程序:

    • 在主程序中，调用了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)

二次优化—源码解析

这段代码的目的是找出一个给定数字的两个质数因子。下面是对代码的详细分析：

  1. 导入模块:

    • math: 这个模块提供了数学函数，但在这个代码中并没有被使用。

    • time: 这个模块被用来测量程序的执行时间。

  2. is_prime函数:

    • 这个函数用于判断一个数是否为质数。

    • 它从2开始，一直检查到n-1，看n是否能被这些数整除。如果能，则n不是质数，返回False；否则，返回True。

    • 但这个函数可以优化。例如，只需要检查到sqrt(n)就可以了，因为如果n有一个大于sqrt(n)的因子，那么它必然还有一个小于或等于sqrt(n)的因子。

  3. prime_pq函数:

    • 这个函数用于找出一个数的两个质数因子。

    • 它从1开始，遍历到n-1，对于每个数p，再遍历从1到n-1的每个数q。

    • 如果p和q都是质数，并且它们的乘积等于n，那么就找到了两个质数因子，打印出来并结束程序。

    • 这个函数的时间复杂度是O(n^2)，因为它有两个嵌套的循环。对于大的n，这可能会非常慢。

  4. 主程序:

    • 在主程序中，调用了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)

三次优化—源码解析

这段代码的目的是找出一个给定数字的两个质数因子。下面是对代码的详细分析：

  1. 导入模块:

    • math: 这个模块提供了数学函数，但在这个代码中并没有被使用。

    • time: 这个模块被用来测量程序的执行时间。

  2. is_prime函数:

    • 这个函数用于判断一个数是否为质数。

    • 首先排除小于2的数，因为它们不是质数。

    • 对于2这个特殊的数，直接返回True。

    • 对于偶数（除了2），直接返回False。

    • 然后从3开始，只检查奇数（因为偶数已经被排除了），直到sqrt(n)。

    • 如果在这个范围内找到一个能整除n的数，那么n就不是质数，返回False；否则，返回True。

  3. prime_pq函数:

    • 这个函数用于找出一个数的两个质数因子。

    • 它从1开始，遍历到n-1，对于每个数p，再遍历从1到n-1的每个数q。

    • 如果p和q都是质数，并且它们的乘积等于n，那么就找到了两个质数因子，打印出来并结束程序。

    • 这个函数的时间复杂度是O(n^2)，因为它有两个嵌套的循环。对于大的n，这可能会非常慢。

  4. 主程序:

    • 在主程序中，调用了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)

四次优化—源码解析

这段代码的目的是找出一个给定数字的两个质数因子。下面是对代码的详细分析：

  1. 导入模块:

    • math: 这个模块提供了数学函数，但在这个代码中并没有被使用。

    • time: 这个模块被用来测量程序的执行时间。

  2. is_prime函数:

    • 这个函数用于判断一个数是否为质数。

    • 它从2开始，一直检查到n-1，看n是否能被这些数整除。如果能，则n不是质数，返回False；否则，返回True。

    • 但这个函数可以优化。例如，只需要检查到sqrt(n)就可以了，因为如果n有一个大于sqrt(n)的因子，那么它必然还有一个小于或等于sqrt(n)的因子。

  3. prime_pq函数:

    • 这个函数用于找出一个数的两个质数因子。

    • 它从1开始，遍历到n-1，对于每个数p，再遍历从1到n-1的每个数q。

    • 如果p和q都是质数，并且它们的乘积等于n，那么就找到了两个质数因子，打印出来并结束程序。

    • 这个函数的时间复杂度是O(n^2)，因为它有两个嵌套的循环。对于大的n，这可能会非常慢。

  4. 主程序:

    • 在主程序中，调用了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)

五次优化—源码解析

这段代码的目的是找出一个给定数字的两个质数因子。下面是对代码的详细分析：

  1. 导入模块:

    • math: 这个模块提供了数学函数，但在这个代码中并没有被使用。

    • time: 这个模块被用来测量程序的执行时间。

  2. is_prime函数:

    • 这个函数用于判断一个数是否为质数。

    • 它从2开始，一直检查到n-1，看n是否能被这些数整除。如果能，则n不是质数，返回False；否则，返回True。

    • 但这个函数可以优化。例如，只需要检查到sqrt(n)就可以了，因为如果n有一个大于sqrt(n)的因子，那么它必然还有一个小于或等于sqrt(n)的因子。

  3. prime_pq函数:

    • 这个函数用于找出一个数的两个质数因子。

    • 它从1开始，遍历到n-1，对于每个数p，再遍历从1到n-1的每个数q。

    • 如果p和q都是质数，并且它们的乘积等于n，那么就找到了两个质数因子，打印出来并结束程序。

    • 这个函数的时间复杂度是O(n^2)，因为它有两个嵌套的循环。对于大的n，这可能会非常慢。

  4. 主程序:

    • 在主程序中，调用了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)

六次优化—源码解析

这段代码的目的是找出一个给定数字的两个质数因子。下面是对代码的详细分析：

  1. 导入模块:

    • math: 这个模块提供了数学函数，但在这个代码中并没有被使用。

    • time: 这个模块被用来测量程序的执行时间。

  2. is_prime函数:

    • 这个函数用于判断一个数是否为质数。

    • 首先排除小于2的数，因为它们不是质数。

    • 对于2这个特殊的数，直接返回True。

    • 对于偶数（除了2），直接返回False。

    • 然后从3开始，只检查奇数（因为偶数已经被排除了），直到sqrt(n)。

    • 如果在这个范围内找到一个能整除n的数，那么n就不是质数，返回False；否则，返回True。

  3. prime_pq函数:

    • 这个函数用于找出一个数的两个质数因子。

    • 它从1开始，遍历到n-1，对于每个数p，再遍历从1到n-1的每个数q。

    • 如果p和q都是质数，并且它们的乘积等于n，那么就找到了两个质数因子，打印出来并结束程序。

    • 这个函数的时间复杂度是O(n^2)，因为它有两个嵌套的循环。对于大的n，这可能会非常慢。

  4. 主程序:

    • 在主程序中，调用了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)

七次优化—源码解析

这段代码的目的是找出一个给定数字的两个质数因子。下面是对代码的详细分析：

  1. 导入模块:

    • math: 这个模块提供了数学函数，但在这个代码中并没有被使用。

    • time: 这个模块被用来测量程序的执行时间。

  2. is_prime函数:

    • 这个函数用于判断一个数是否为质数。

    • 首先排除小于2的数，因为它们不是质数。

    • 对于2这个特殊的数，直接返回True。

    • 对于偶数（除了2），直接返回False。

    • 然后从3开始，只检查奇数（因为偶数已经被排除了），直到sqrt(n)。

    • 如果在这个范围内找到一个能整除n的数，那么n就不是质数，返回False；否则，返回True。

  3. prime_pq函数:

    • 这个函数用于找出一个数的两个质数因子。

    • 它从1开始，遍历到n-1，对于每个数p，再遍历从1到n-1的每个数q。

    • 如果p和q都是质数，并且它们的乘积等于n，那么就找到了两个质数因子，打印出来并结束程序。

    • 这个函数的时间复杂度是O(n^2)，因为它有两个嵌套的循环。对于大的n，这可能会非常慢。

  4. 主程序:

    • 在主程序中，调用了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)

八次优化—源码解析

这段代码的目的是找出一个给定数字的两个质数因子。下面是对代码的详细分析：

  1. 导入模块:

    • math: 这个模块提供了数学函数，但在这个代码中并没有被使用。

    • time: 这个模块被用来测量程序的执行时间。

  2. is_prime函数:

    • 这个函数用于判断一个数是否为质数。

    • 它从2开始，一直检查到n-1，看n是否能被这些数整除。如果能，则n不是质数，返回False；否则，返回True。

    • 但这个函数可以优化。例如，只需要检查到sqrt(n)就可以了，因为如果n有一个大于sqrt(n)的因子，那么它必然还有一个小于或等于sqrt(n)的因子。

  3. prime_pq函数:

    • 这个函数用于找出一个数的两个质数因子。

    • 它从1开始，遍历到n//2 + 1，对于每个数p，再遍历从1到n//2 + 1的每个数q。

    • 如果p和q都是质数，并且它们的乘积等于n，那么就找到了两个质数因子，打印出来并结束程序。

    • 这个函数的时间复杂度是O(n^2)，因为它有两个嵌套的循环。对于大的n，这可能会非常慢。

  4. 主程序:

    • 在主程序中，调用了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)

九次优化—源码解析

这段代码的目的是找出一个给定数字的两个质数因子。下面是对代码的详细分析：

  1. 导入模块:

    • math: 这个模块提供了数学函数，但在这个代码中并没有被使用。

    • time: 这个模块被用来测量程序的执行时间。

  2. is_prime函数:

    • 这个函数用于判断一个数是否为质数。

    • 它从2开始，一直检查到n-1，看n是否能被这些数整除。如果能，则n不是质数，返回False；否则，返回True。

    • 但这个函数可以优化。例如，只需要检查到sqrt(n)就可以了，因为如果n有一个大于sqrt(n)的因子，那么它必然还有一个小于或等于sqrt(n)的因子。

  3. prime_pq函数:

    • 这个函数用于找出一个数的两个质数因子。

    • 它从1开始，遍历到n//2 + 1，对于每个数p，再遍历从1到n//2 + 1的每个数q。

    • 如果p和q都是质数，并且它们的乘积等于n，那么就找到了两个质数因子，打印出来并结束程序。

    • 这个函数的时间复杂度是O(n^2)，因为它有两个嵌套的循环。对于大的n，这可能会非常慢。

  4. 主程序:

    • 在主程序中，调用了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)

十次优化—源码解析

这段代码的目的是找出一个给定数字的两个质数因子。下面是对代码的详细分析：

  1. 导入模块:

    • math: 这个模块提供了数学函数，但在这个代码中并没有被使用。

    • time: 这个模块被用来测量程序的执行时间。

  2. is_prime函数:

    • 这个函数用于判断一个数是否为质数。

    • 首先排除小于2的数，因为它们不是质数。

    • 对于2这个特殊的数，直接返回True。

    • 对于偶数（除了2），直接返回False。

    • 然后从3开始，只检查奇数（因为偶数已经被排除了），直到sqrt(n)。

    • 如果在这个范围内找到一个能整除n的数，那么n就不是质数，返回False；否则，返回True。

  3. prime_pq函数:

    • 这个函数用于找出一个数的两个质数因子。

    • 它从1开始，遍历到n//2 + 1，对于每个数p，再遍历从1到n//2 + 1的每个数q。

    • 如果p和q都是质数，并且它们的乘积等于n，那么就找到了两个质数因子，打印出来并结束程序。

    • 这个函数的时间复杂度是O(n^2)，因为它有两个嵌套的循环。对于大的n，这可能会非常慢。

  4. 主程序:

    • 在主程序中，调用了prime_pq02函数，传入的参数是99460729。

优化建议:

  1. 优化is_prime函数，只需要检查到sqrt(n)就可以了。

  2. 对于prime_pq02函数，可以考虑使用更高效的算法，如试除法结合埃拉托斯特尼筛法来找出质数因子。

  3. 可以添加更多的错误检查和边界条件处理，例如检查输入的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)

十一次优化—源码解析

这段代码的目的是找出一个给定数字的两个质数因子。下面是对代码的详细分析：

  1. 导入模块:

    • math: 这个模块提供了数学函数，但在这个代码中并没有被使用。

    • time: 这个模块被用来测量程序的执行时间。

  2. is_prime函数:

    • 这个函数用于判断一个数是否为质数。

    • 首先排除小于2的数，因为它们不是质数。

    • 对于2这个特殊的数，直接返回True。

    • 对于偶数（除了2），直接返回False。

    • 然后从3开始，只检查奇数（因为偶数已经被排除了），直到sqrt(n)。

    • 如果在这个范围内找到一个能整除n的数，那么n就不是质数，返回False；否则，返回True。

  3. prime_pq函数:

    • 这个函数用于找出一个数的两个质数因子。

    • 它从1开始，遍历到n//2 + 1，对于每个数p，再遍历从1到n//2 + 1的每个数q。

    • 如果p和q都是质数，并且它们的乘积等于n，那么就找到了两个质数因子，打印出来并结束程序。

    • 这个函数的时间复杂度是O(n^2)，因为它有两个嵌套的循环。对于大的n，这可能会非常慢。

  4. 主程序:

    • 在主程序中，调用了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)

十二次优化—源码解析

这段代码的目的是找出一个给定数字的两个质数因子。下面是对代码的详细分析：

  1. 导入模块:

    • math: 这个模块提供了数学函数，但在这个代码中并没有被使用。

    • time: 这个模块被用来测量程序的执行时间。

  2. is_prime函数:

    • 这个函数用于判断一个数是否为质数。

    • 它从2开始，一直检查到n-1，看n是否能被这些数整除。如果能，则n不是质数，返回False；否则，返回True。

    • 但这个函数可以优化。例如，只需要检查到sqrt(n)就可以了，因为如果n有一个大于sqrt(n)的因子，那么它必然还有一个小于或等于sqrt(n)的因子。

  3. prime_pq函数:

    • 这个函数用于找出一个数的两个质数因子。

    • 它从2开始，遍历到n的平方根加1，对于每个数p，如果n能被p整除，那么计算q = n // p。

    • 然后检查p和q是否都是质数，如果是，则打印出这两个质数因子，并结束程序。

    • 这个函数的时间复杂度是O(n^2)，因为它有两个嵌套的循环。对于大的n，这可能会非常慢。

  4. 主程序:

    • 在主程序中，调用了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)

十三次优化—源码解析

这段代码的目的是找出一个给定数字的两个质数因子。下面是对代码的详细分析：

  1. 导入模块:

    • math: 这个模块提供了数学函数，但在这个代码中并没有被使用。

    • time: 这个模块被用来测量程序的执行时间。

  2. is_prime函数:

    • 这个函数用于判断一个数是否为质数。

    • 它从2开始，一直检查到n-1，看n是否能被这些数整除。如果能，则n不是质数，返回False；否则，返回True。

    • 但这个函数可以优化。例如，只需要检查到sqrt(n)就可以了，因为如果n有一个大于sqrt(n)的因子，那么它必然还有一个小于或等于sqrt(n)的因子。

  3. prime_pq函数:

    • 这个函数用于找出一个数的两个质数因子。

    • 它从2开始，遍历到n的平方根加1，对于每个数p，如果n能被p整除，那么计算q = n // p。

    • 然后检查p和q是否都是质数，如果是，则打印出这两个质数因子，并结束程序。

    • 这个函数的时间复杂度是O(n^2)，因为它有两个嵌套的循环。对于大的n，这可能会非常慢。

  4. 主程序:

    • 在主程序中，调用了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)

十四次优化—源码解析

这段代码的目的是找出一个给定数字的两个质数因子。下面是对代码的详细分析：

  1. 导入模块:

    • math: 这个模块提供了数学函数，但在这个代码中并没有被使用。

    • time: 这个模块被用来测量程序的执行时间。

  2. is_prime函数:

    • 这个函数用于判断一个数是否为质数。

    • 首先排除小于2的数，因为它们不是质数。

    • 对于2这个特殊的数，直接返回True。

    • 对于偶数（除了2），直接返回False。

    • 然后从3开始，只检查奇数（因为偶数已经被排除了），直到sqrt(n)。

    • 如果在这个范围内找到一个能整除n的数，那么n就不是质数，返回False；否则，返回True。

  3. prime_pq函数:

    • 这个函数用于找出一个数的两个质数因子。

    • 它从2开始，遍历到n的平方根加1，对于每个数p，如果n能被p整除，那么计算q = n // p。

    • 然后检查p和q是否都是质数，如果是，则打印出这两个质数因子，并结束程序。

    • 这个函数的时间复杂度是O(n^2)，因为它有两个嵌套的循环。对于大的n，这可能会非常慢。

  4. 主程序:

    • 在主程序中，调用了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)

最终优化—源码解析

这段代码的目的是找出一个给定数字的两个质数因子。下面是对代码的详细分析：

  1. 导入模块:

    • math: 这个模块提供了数学函数，但在这个代码中并没有被使用。

    • time: 这个模块被用来测量程序的执行时间。

  2. is_prime函数:

    • 这个函数用于判断一个数是否为质数。

    • 首先排除小于2的数，因为它们不是质数。

    • 对于2这个特殊的数，直接返回True。

    • 对于偶数（除了2），直接返回False。

    • 然后从3开始，只检查奇数（因为偶数已经被排除了），直到sqrt(n)。

    • 如果在这个范围内找到一个能整除n的数，那么n就不是质数，返回False；否则，返回True。

  3. prime_pq函数:

    • 这个函数用于找出一个数的两个质数因子。

    • 它从2开始，遍历到n的平方根加1，对于每个数p，如果n能被p整除，那么计算q = n // p。

    • 然后检查p和q是否都是质数，如果是，则打印出这两个质数因子，并结束程序。

    • 这个函数的时间复杂度是O(n^2)，因为它有两个嵌套的循环。对于大的n，这可能会非常慢。

  4. 主程序:

    • 在主程序中，调用了prime_pq函数，传入的参数是99460729。

高阶优化

思路：

1、优化is_prime函数，只需要检查到sqrt(n)就可以了。
2、prime_pq函数，可以考虑使用更高效的算法，如试除法结合埃拉托斯特尼筛法/Pollard's rho算法来找出质数因子。
3、并行化处理在多核处理器上运行，可以将筛选质数或者试除的过程进行并行化，进一步提高效率。
4、添加更多的错误检查和边界条件处理，例如检查输入的n是否为正整数。

以后有时间再来演示高阶算法。

http://www.lryc.cn/news/521314.html

相关文章：

  • Mysql--重点篇--索引（索引分类，Hash和B-tree索引，聚簇和非聚簇索引，回表查询，覆盖索引，索引工作原理，索引失效，索引创建原则等）
  • matlab使用 BP 神经网络进行数据预测的完整流程，包括数据读取、数据预处理等等
  • systemd-networkd NetworkManager 介绍
  • 本地部署项目管理工具 Leantime 并实现外部访问
  • PHP cURL 函数初学者完全指南
  • C#中的Array数组,List集合和ArrayList集合--07
  • 基于深度学习的视觉检测小项目（十三） 资源文件的生成和调用
  • 硬件实用技巧：TPS54331DR横杠标识识别1引脚
  • 《C++11》nullptr介绍：从NULL说起
  • 自然语言处理基础：全面概述
  • 网络安全的几种攻击方法
  • 国内源快速在线安装qt5.15以上版本。（10min安装好）（图文教程）
  • 【pycharm发现找不到python打包工具,且无法下载】
  • C++ QT 自绘表盘
  • 数据科学与数据工程：两者的区别与交集
  • MAC AndroidStudio模拟器无网络
  • PHP语言的多线程编程
  • 当自动包布机遇上Profinet转ModbusTCP网关，“妙啊”，工业智能“前景无限
  • 浅析大语言模型安全和隐私保护国内外标准和政策
  • OpenCV相机标定与3D重建(54)解决透视 n 点问题（Perspective-n-Point, PnP）函数solvePnP()的使用
  • Chatper 4: Implementing a GPT model from Scratch To Generate Text
  • spring-mvc源码分析v3.3.0
  • Rust实现智能助手 - 项目初始化
  • sparkSQL练习
  • QT跨平台应用程序开发框架（2）—— 初识QT
  • [创业之路-248]：《华为流程变革：责权利梳理与流程体系建设》华为流程的前端拉动后端，与计算机软件的前端应用与后端程序的类比关系
  • 汇总统计数据--SQL中聚集函数的使用
  • 【C盘清理】C盘清理工具、Unity缓存文件转移
  • C# 迭代,递归,回调--13
  • 海康大数据面试题及参考答案