一个认为一切根源都是“自己不够强”的INTJ

个人主页：用哲学编程-CSDN博客
专栏：每日一题——举一反三
Python编程学习
Python内置函数

Python-3.12.0文档解读

题目链接

目录

我的写法

代码点评

代码分析

时间复杂度分析

空间复杂度分析

优化建议

我要更强！

代码解释

时间复杂度和空间复杂度分析

哲学和编程思想

举一反三

1. 效率优化

2. 预计算和缓存

3. 算法设计

4. 数学思维

---

我的写法

from math import*
N=int(input())
def is_prime(n):
    if n <= 1:
        return 0
    if n <= 3:
        return 1
    if n % 2 == 0 or n % 3 == 0:
        return 0
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return 0
        i += 6
    return 1
output=0
for i in range(3,N+1-2,2):
    if is_prime(i)+is_prime(i+2)==2:
        output+=1
print(output)

---

代码点评

这段代码的主要功能是计算小于或等于给定整数 N 的范围内，有多少对连续的奇数都是质数。代码中定义了一个辅助函数 is_prime(n) 来判断一个数是否为质数，并使用这个函数来检查每对连续的奇数。

代码分析

1. 输入处理：
   • 使用 input() 函数获取用户输入，并将其转换为整数。
2. 质数判断函数 is_prime(n)：
   • 如果 n 小于等于 1，返回 0（非质数）。
   • 如果 n 小于等于 3，返回 1（质数）。
   • 如果 n 能被 2 或 3 整除，返回 0（非质数）。
   • 使用一个循环从 5 开始，检查 n 是否能被 i 或 i + 2 整除，直到 i * i 大于 n。如果找到任何因子，返回 0；否则，返回 1。
3. 主逻辑：
   • 初始化输出计数器 output 为 0。
   • 使用一个循环从 3 开始，每次增加 2（因为只需要检查奇数），直到 N。
   • 在循环中，检查当前奇数和下一个奇数是否都是质数，如果是，则增加计数器。
4. 输出结果：

• 循环结束后，打印输出计数器的值。

  时间复杂度分析

  • 质数判断函数 is_prime(n)：这个函数的时间复杂度是 O(sqrt(n))，因为最坏情况下，需要检查到 sqrt(n) 来确定 n 是否为质数。
  • 主循环：循环从 3 到 N，每次增加 2，因此循环次数大约是 N/2。
  • 总体时间复杂度：每次循环中调用两次 is_prime 函数，因此总体时间复杂度是 O(N * sqrt(N))。

    空间复杂度分析

    • 代码中没有使用额外的数据结构来存储大量数据，只使用了几个变量（N、output、循环变量 i），因此空间复杂度是 O(1)。

      优化建议

      • 可以考虑使用更高效的质数判断算法，例如埃拉托斯特尼筛法，虽然对于单个数的判断可能不是最优，但对于多次调用质数判断函数的情况，预先计算并存储质数表可能更高效。
      • 对于大范围的质数检查，可以考虑并行化处理，利用多核处理器提高计算效率。

        总体来说，这段代码是一个有效的解决方案，但在处理非常大的 N 时可能会遇到性能瓶颈。

        ---

        我要更强！

        为了优化时间复杂度和空间复杂度，我们可以采取以下策略：

        1. 预计算质数：预先计算并存储小于 N 的所有质数，这样可以避免在主循环中重复调用 is_prime 函数。
        2. 使用质数列表：通过遍历质数列表来找到满足条件的质数对，而不是遍历所有奇数。

        下面是优化后的代码：

        from math import sqrt
        # 输入处理
        N = int(input())
        # 生成质数列表
        def generate_primes(max_n):
            primes = []
            sieve = [True] * (max_n + 1)
            for x in range(2, int(sqrt(max_n)) + 1):
                if sieve[x]:
                    primes.append(x)
                    for u in range(x * x, max_n + 1, x):
                        sieve[u] = False
            for x in range(int(sqrt(max_n)) + 1, max_n + 1):
                if sieve[x]:
                    primes.append(x)
            return primes
        # 获取小于等于N的所有质数
        prime_list = generate_primes(N)
        # 计算质数对的数量
        output = 0
        for i in range(1, len(prime_list) - 1):
            if prime_list[i] - prime_list[i - 1] == 2:
                output += 1
        # 输出结果
        print(output)

        代码解释

        1. 输入处理：与之前相同。
        2. 生成质数列表：
           • 使用埃拉托斯特尼筛法生成小于等于 N 的所有质数。这个函数首先创建一个布尔数组 sieve 来标记每个数是否为质数。
           • 然后，从 2 开始，标记所有质数的倍数为非质数。
           • 最后，将所有标记为质数的数添加到 primes 列表中。
        3. 计算质数对的数量：
           • 遍历质数列表，检查每对相邻的质数之间的差是否为 2。如果是，则增加计数器。
        4. 输出结果：与之前相同。

        时间复杂度和空间复杂度分析

        • 时间复杂度：生成质数列表的时间复杂度是 O(N log(log N))，这是埃拉托斯特尼筛法的复杂度。遍历质数列表的时间复杂度是 O(N)。因此，总体时间复杂度是 O(N log(log N))。
        • 空间复杂度：需要存储所有小于等于 N 的质数，因此空间复杂度是 O(N)。

          这种优化方法在处理大数 N 时比原始方法更高效，因为它避免了重复的质数检查，并且直接在预计算的质数列表上操作。

          ---

          哲学和编程思想

          这种方法体现了几个重要的哲学和编程思想：

          1. 效率优化：这种方法的核心在于优化算法的时间和空间复杂度，这是计算机科学中的一个基本原则。通过减少不必要的计算和存储，提高程序的运行效率，反映了“效率至上”的哲学思想。
          2. 预计算和缓存：预先计算并存储质数列表，以便在后续计算中重复使用，这是一种常见的优化策略，称为“缓存”或“记忆化”。这种思想在计算机科学中广泛应用，特别是在动态规划和函数式编程中。
          3. 算法设计：使用埃拉托斯特尼筛法生成质数列表，这是一种经典的算法设计。它体现了算法设计中的“分治”思想，通过逐步排除非质数，最终得到所有质数。
          4. 数学思维：这种方法依赖于数学上的质数性质，如质数分布的规律和质数检查的数学原理。这反映了编程和数学之间的紧密联系，数学思维在算法设计中起着至关重要的作用。
          5. 迭代改进：从最初的方法到优化后的方法，这是一个迭代改进的过程。每次改进都基于对现有方法的分析和理解，逐步逼近更优的解决方案。这种迭代改进的思想是软件工程和编程实践中的一个重要原则。
          6. 抽象和模块化：代码中将质数生成和质数对计数分别封装在不同的函数中，体现了抽象和模块化的编程思想。这种设计使得代码更易于理解和维护，同时也提高了代码的可复用性。

          ---

          举一反三

          根据上述的哲学和编程思想，以下是一些技巧和示例代码，举一反三应用到其他编程问题中：

          1. 效率优化

          # 原始方法：线性搜索
          def find_element(lst, target):
              for i in range(len(lst)):
                  if lst[i] == target:
                      return i
              return -1
          # 优化方法：使用集合提高搜索效率
          def find_element_optimized(lst, target):
              elements_set = set(lst)
              if target in elements_set:
                  return lst.index(target)
              return -1
          # 测试
          lst = [1, 2, 3, 4, 5]
          target = 3
          print(find_element(lst, target))  # 输出: 2
          print(find_element_optimized(lst, target))  # 输出: 2

          2. 预计算和缓存

          示例： 斐波那契数列计算

          # 原始方法：递归计算
          def fib(n):
              if n <= 1:
                  return n
              else:
                  return fib(n-1) + fib(n-2)
          # 优化方法：使用缓存（记忆化）
          def fib_optimized(n, memo={}):
              if n <= 1:
                  return n
              elif n not in memo:
                  memo[n] = fib_optimized(n-1, memo) + fib_optimized(n-2, memo)
              return memo[n]
          # 测试
          n = 10
          print(fib(n))  # 输出: 55
          print(fib_optimized(n))  # 输出: 55

          3. 算法设计

          示例： 数组中的最大子数组和

          # 原始方法：暴力搜索
          def max_subarray(nums):
              max_sum = float('-inf')
              for i in range(len(nums)):
                  for j in range(i, len(nums)):
                      max_sum = max(max_sum, sum(nums[i:j+1]))
              return max_sum
          # 优化方法：使用动态规划
          def max_subarray_optimized(nums):
              max_sum = current_sum = nums[0]
              for num in nums[1:]:
                  current_sum = max(num, current_sum + num)
                  max_sum = max(max_sum, current_sum)
              return max_sum
          # 测试
          nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
          print(max_subarray(nums))  # 输出: 6
          print(max_subarray_optimized(nums))  # 输出: 6

          4. 数学思维

          示例： 判断一个数是否为完美数

          # 原始方法：遍历所有可能的因子
          def is_perfect_number(n):
              sum_of_divisors = 0
              for i in range(1, n):
                  if n % i == 0:
                      sum_of_divisors += i
              return sum_of_divisors == n
          # 优化方法：利用数学性质减少计算
          def is_perfect_number_optimized(n):
              if n <= 1:
                  return False
              sum_of_divisors = 1
              for i in range(2, int(n**0.5) + 1):
                  if n % i == 0:
                      sum_of_divisors += i
                      if i != n // i:
                          sum_of_divisors += n // i
              return sum_of_divisors == n
          # 测试
          n = 28
          print(is_perfect_number(n))  # 输出: True
          print(is_perfect_number_optimized(n))  # 输出: True

          ---

          感谢阅读。