整除、因数与质数——从分糖果开始学数论

你有没有分过糖果？如果一班有12颗糖，要分给3个小朋友，每人正好分到4颗，一颗不多一颗不少——这在数学上就叫“整除”。生活中类似的例子还有很多：排座位、切披萨、计算零花钱……从这些小事中，数学家总结出了几个重要的概念：整除、因数、质数。掌握了它们，你就能轻松解决很多编程和数学问题，比如判断“一个数是不是质数”“两个数有没有公因数”等等。

整除——像分糖果一样刚刚好

定义：如果a除以b的余数是0，我们就说“b能整除a”，或者说“a是b的倍数，b是a的因数”。

比如：

12颗糖分给3个人，每人4颗。检查：12 ÷ 3 = 4，余数为0。所以3整除12，3是12的因数，12是3的倍数。
20块饼干分给6个人，每人3块还剩2块（20÷6=3余2），余数不是0，所以6不能整除20。

在编程中，我们使用取模运算符 % 判断整除：

# 判断12能否被3整除
a = 12       # 被除数
b = 3        # 除数
if a % b == 0:
    print(f"{b}能整除{a}，商是{a // b}")
else:
    print(f"{b}不能整除{a}，余数是{a % b}")

输出：3能整除12，商是4

生活中的整除：零花钱每天5元，那么15元能花多少天？15÷5=3天，正好花完（整除）。如果每天花4元，15元能花3天还剩3元，就不整除。

因数——能“整除”一个数的数

一个数的因数，就是所有能整除这个数的数（包括1和它本身）。

比如求8的因数：

8÷1=8，余0 → 1和8都是因数
8÷2=4，余0 → 2和4都是因数
8÷3≠整数，不是因数
8÷4=2，余0 → 4前面已经出现，停止

所以8的因数有：1, 2, 4, 8（共4个）。

生活例子：18名学生排成方队，可以排成几行几列？行数和列数都是18的因数：1×18、2×9、3×6、6×3,9×2,18×1，所以可能的队形有1行18列、2行9列、3行6列等。

代码：找一个数的所有因数

def find_factors(n):
    # 输出n的所有因数
    factors = []           # 存储因数的列表
    i = 1                  # 从1开始检查
    while i <= n:
        if n % i == 0:     # 如果能整除 i，说明i是因数
            factors.append(i)
        i += 1
    return factors

num = 18                   # 要检查的数
print(f"{num}的因数有：{find_factors(num)}")

输出：18的因数有：[1, 2, 3, 6, 9, 18]

质数与合数——因数数量的“分水岭”

根据因数个数的多少，大于1的自然数可以分成两类：

质数(素数)：只有1和它本身两个因数。例如2（因数1和2）、3（1和3）、5、7、11、13……
合数：除了1和它本身，还有别的因数（即至少有三个因数）。例如4（1,2,4）、6（1,2,3,6）、8（1,2,4,8）……

特别注意：

最小的质数是 2，它也是唯一的偶质数（因为其他偶数都能被2整除，所以都是合数）。
1既不是质数也不是合数，因为它只有1个因数（1）。

生活例子：质数就像“独一无二”的个体——只有自己和自己作伴；合数就像“有朋友”的数。比如排队：如果全班人数是质数（如17人），就无法排成人数相等的矩形队列（除非1行或1列）；如果是合数（如18人），就能排成2×9或3×6等整齐方阵。

判断质数：最朴素的方法是从2检查到n-1，看有没有因数。但我们可以优化：只需要检查到平方根即可（因为如果n = a×b，且a≤b，那么a一定≤√n）。

下面的函数用从2到√n的循环判断：

def is_prime(n):
    # 判断n是否为质数，是返回True，否返回False
    if n < 2:                # 小于2的数（0,1）不是质数
        return False
    i = 2                    # 从2开始检查
    while i * i <= n:        # i 的平方 小于等于 n
        if n % i == 0:       # 如果能整除，说明有因数
            return False     # 不是质数
        i += 1               # 检查下一个数
    return True              # 循环结束都没有因数，是质数

# 测试几个数
print(is_prime(17))   # 输出 True
print(is_prime(20))   # 输出 False（有因数2,4,5,10）
print(is_prime(2))    # 输出 True（最小质数）
print(is_prime(1))    # 输出 False（1不是质数）

为什么检查到√n就够了？举例：找24的质数性，√24≈4.9，只需检查2、3、4。如果2不是因数，那么也不可能有大于24/2=12的因数（因为任何因数对中，至少有一个≤√n）。

新手最容易犯的错误

把1当成质数。记住：质数必须大于1，且只有2个因数。1只有一个因数，所以不是质数。
忘记检查2的特殊性。有的同学写循环从2到n-1，但没处理n=2的情况。实际上循环条件while i*i <= n会自动跳过（因为4>2），返回True，所以正确。但要注意n<2时直接返回False。
循环范围多写一个。比如检查到n本身，会返回False（因为n%n==0），导致正确质数被判为合数。记住：只检查到√n（含）。
把小数的平方根搞错。在Python中可以用int(n**0.5)，但用while i*i <= n更安全，避免了浮点误差。

完整示例：输出100以内的所有质数

下面是一个完整的程序，它利用is_prime函数，找出1到100之间所有的质数，并一行行打印出来。

def is_prime(n):
    # 判断n是否为质数
    if n < 2:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

# 主程序：输出100以内的质数
limit = 100                  # 上限
print(f"1到{limit}之间的质数有：")
for num in range(1, limit+1):
    if is_prime(num):
        print(num, end=" ")  # 不换行，用空格隔开
print()                      # 最后换行

# 同时统计个数
count = 0
for num in range(1, limit+1):
    if is_prime(num):
        count += 1
print(f"共有{count}个质数。")

输出：

1到100之间的质数有：
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 
共有25个质数。

整除、因数与质数