每日一练：质因数分解

1. 题目

  从键盘输入一个整数，开始整数的质因数分解，最后打印出该整数的所有质因数。

2.解题思路

  1）初始化： 从最小的质数开始，将输入的整数不断除以质数，直到无法整除为止。
  2）循环： 用一个循环来迭代质数，每次检查输入的整数是否能整除当前的质数。
  3）整除时： 如果整除，将这个质数加入结果列表，并将输入的整数更新为除以这个质数后的值。
  4）无法整除时： 如果不能整除，就将质数加一，然后重复步骤2。
  5）终止条件： 当输入的整数变为1时，表示已经无法再继续分解，结束循环。

3. 代码实现

3.1 实现方式一：正常解题思路

  按上述正常解题思路实现。

def prime_factors(n):
    factors = []  # 存储质因数的列表
    divisor = 2    # 起始的质数
    while divisor <= n:
        if n % divisor == 0:
            factors.append(divisor)
            n = n // divisor
        else:
            divisor += 1
    return factors

# 输入一个整数
num = int(input("请输入一个整数："))
# 获取质因数
result = prime_factors(num)
# 输出结果
print(f"{num}的质因数为：{result}")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3.2 代码实现二：递归调用

  递归是一种解决问题的方法，其中一个函数调用自身，通常以解决规模较小的子问题为基础。在质因数分解的递归实现中，函数通过不断地调用自身来逐步解决子问题，直到达到终止条件。

def prime_factors_recursive(n, divisor=2):
    # 基本情况：n等于1时返回空列表
    if n == 1:
        return []
    # 整除情况
    elif n % divisor == 0:
        return [divisor] + prime_factors_recursive(n // divisor, divisor)
    # 不整除情况
    else:
        # 增加divisor的值，然后递归调用
        return prime_factors_recursive(n, divisor + 1)

# 输入一个整数
num = int(input("请输入一个整数："))
# 获取质因数
result = prime_factors_recursive(num)
# 输出结果
print(f"{num}的质因数为：{result}")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3.3 代码实现三：试除法

  试除法是一种通过测试每个可能的除数是否是给定整数的质因数的方法。
  在试除时只需要测试到质数的平方根，从而减少了循环的次数。

def prime_factors_optimized(n):
    factors = []
    divisor = 2
    while divisor * divisor <= n:
        if n % divisor == 0:
            factors.append(divisor)
            n = n // divisor
        else:
            divisor += 1
    if n > 1:
        factors.append(n)
    return factors

# 输入一个整数
num = int(input("请输入一个整数："))
# 获取质因数
result = prime_factors_optimized(num)
# 输出结果
print(f"{num}的质因数为：{result}")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19