ex15 质数与因数分解

要学习的知识点

质数、合数与 1 的定义
平方根范围内试除
不同质因数分解
整除和反复除尽
break 与 while

题目

练习 15：判断正整数是否为质数；若不是，列出所有不同的质因数。

参考程序：ex15.py；空白练习：lx15.py。

完整代码

以下内容与 ex15.py 一致，可对照右侧讲解阅读。

"""练习 15：判断正整数是否为质数；若不是，列出所有不同的质因数。

学习说明：
- 质数是大于 1 且只有 1 和自身两个正因数的整数；1 不是质数也不是合数。
- 若 n 有一个大于 sqrt(n) 的因数，必有一个对应的小于 sqrt(n) 的因数，故只需检查平方根以内。
- 找质因数时，每找到一个因数就反复除尽它，列表中因此只记录不同质因数。
- 最后若 remaining 大于 1，它本身就是一个尚未记录的质因数。
"""
n = int(input())
if n < 1:
    raise ValueError("请输入正整数")

is_prime = n >= 2
if n >= 2:
    divisor = 2
    # divisor * divisor <= n 等价于 divisor 不超过 n 的平方根，避免调用浮点平方根。
    while divisor * divisor <= n:
        if n % divisor == 0:
            is_prime = False
            break
        divisor += 1

print("prime:", "yes" if is_prime else "no")

remaining = n
prime_factors = []
divisor = 2
# 每个因数只加入一次，但需要除尽它的所有幂次。
while divisor * divisor <= remaining:
    if remaining % divisor == 0:
        prime_factors.append(divisor)
        while remaining % divisor == 0:
            remaining //= divisor
    divisor += 1
if remaining > 1:
    prime_factors.append(remaining)

print("distinct prime factors:", *prime_factors if prime_factors else ["none"])

进阶写法

这版与初学版解决同一道题，使用更精炼的语法或标准库工具。

进阶源码：ex15_adv.py

"""练习 15 进阶版：用 all() 和 math.isqrt() 判断质数。"""
from math import isqrt

n = int(input())
if n < 1:
    raise ValueError("请输入正整数")

is_prime = n > 1 and all(n % divisor != 0 for divisor in range(2, isqrt(n) + 1))
print("prime:", "yes" if is_prime else "no")

remaining = n
prime_factors = []
divisor = 2
while divisor * divisor <= remaining:
    if remaining % divisor == 0:
        prime_factors.append(divisor)
        while remaining % divisor == 0:
            remaining //= divisor
    divisor += 1
if remaining > 1:
    prime_factors.append(remaining)

print("distinct prime factors:", *prime_factors if prime_factors else ["none"])

isqrt(n) 得到整数平方根；all() 只有在所有候选除数都不能整除 n 时才为 True。因数分解仍用循环除尽每种质因数。

运行结果

示例输入：

程序输出：

prime: no
distinct prime factors: 2 3

逐个认识函数

下表根据程序中实际调用的函数和方法整理；自定义函数的实现与算法细节见后续说明。

函数形式	功能与返回值	注意事项
`ValueError(message)`	内置异常类型，用来表示参数值不符合要求。	raise ValueError(...) 会立即抛错并停止当前程序流程。
`input(prompt='')`	读取一行文本，返回 str；若提供 prompt 会先显示提示。	返回值默认是字符串，计算前通常要做类型转换。
`int(value, base=10)`	把整数文本或数值转换为整数。	int('3.5') 不合法；按指定进制解析时可传 base。
`list.append(item)`	在列表末尾追加一个元素；返回 None。	会原地修改列表。
`print(*objects, sep=' ', end='\n')`	把对象转换为文本显示；返回 None。	默认空格分隔并在末尾换行。

为什么检查到平方根就够了

如果 n 可以写成两个整数相乘 n=a*b，那么 a、b 至少有一个不大于平方根。否则两者都大于平方根，乘积就会大于 n。因此找因数只需检查到平方根即可。

程序用 divisor * divisor <= n，避免先算浮点平方根。质数判断找到一个因数就 break；没找到才是质数。

函数和控制语句

写法	作用、参数或返回值	本题说明
`int(input())`	读取文本并转换为整数。	n 必须大于等于 1，否则程序抛 ValueError。
`%` 和 `//`	取余返回余数；整除返回商。	余数为 0 表示找到因数；整除用于把已发现质因数的幂次除尽。
`list.append(item)`	将元素放入列表末尾，返回 None。	找到一个不同质因数时加入列表。
`break`	立即离开最近一层循环。	质数检测找到因数后无需继续检查。
`while`	条件成立就重复执行。	一层循环找因数；内层循环把当前因数的所有次幂除干净。
`print(..., *items)`	将列表解包后输出；条件表达式决定空列表时显示 none。	因数列表为空时用于输入 1 的情况。

找不同质因数的过程

remaining 初始等于 n，divisor 从 2 开始。
若 remaining 能被 divisor 整除，就把 divisor 记录一次。
用内层 while 不断除以 divisor，直到不能整除。这样 12 中的 2 只记录一次。
继续尝试下一个除数。循环结束后若 remaining 大于 1，它是一个剩下的质因数。

n=12：12 ÷ 2 = 6 → 记录 2
       6 ÷ 2 = 3 → 不再重复记录 2
       3 不能被 2 整除；剩余 3 是质因数
不同质因数：[2, 3]

输入 1 时没有质因数；代码输出 none。判断质数时要特别记住 1 的定义。

代码如何运行

先按左侧题目给出的格式输入数据；程序通过 input() 读取，并在需要时转换数据类型。
程序自上而下执行语句；遇到条件、循环或函数调用时，按照右侧算法说明更新变量和处理数据。
最后由 print() 输出计算结果。可将左侧示例输入与输出逐项对照。

先自己跟踪一组小数据，记录循环前后变量的值；这比只看最终答案更容易理解程序。

自己动手试一试

测试 n=1、2、49、97；分别观察 1、合数、较小质数和较大质数。

先在 lx15.py 中独立完成，再运行参考程序比较结果。修改程序时一次只改一个条件或步骤。