质数（质数为什么不包含1）

本文节选自《50个与数学有关的Python编程》。创作结束，最后一篇献上源码。欢迎点赞、关注、收藏。

目录

往期回顾

01 余数

02 约数与倍数

03 质数

正文

第4节 质因数分解

有个问题，素数不包含1，合数也不包含1，1招谁惹谁了？为什么阳间不要，阴间不收呢？这个问题可以用质因数分解来解答。

所谓质因数，其实就是任何一个除1外的正整数，它能分解成所有质数的乘积，如100=2×2×5×5——所有的因子都是质数。

质数还能再分吗？如果将2再分成1×2，那么就还能继续分下去，就成了一个死循环。

在很久以前，1确实被看成一个素数。比如大数学家欧拉就在给朋友的信件中写道：除1外所有的素数……现在数学在定义上认为1既不是素数也不是合数。

题1 直接分解

这个算法比较简单，从2开始，判断N能否被2整除，如果可以，则商作为新的被除数。

n = N = int(input("请输入一个大于1的正整数：")) factor_list = [] while True: sqrt_n = int(pow(n, 0.5)) flag = True for i in range(2,sqrt_n + 1): if n % i == 0: #①能整除 factor_list.append(i) #②把质数存入列表 n /= i #③把商作为新的被除数，继续分解 flag = False break if flag: factor_list.append(int(n)) break print(f"{N}可分解为{factor_list}")

那么问题来了，如数字16，它能2 整除，也能被4整除，4会不会被写入质因数列表呢？答案是：肯定不会。因为一个合数肯定被比它小的质数整除。16先被2整除剩下8，然后重新循环，8又被2整除剩下4，重新循环，4被2整除剩下2……根本没有被4整除的机会。

题2 递归分解

def get_factor(n): sqrt_n = int(pow(n, 0.5)) is_prime = True #1.默认n为素数 for i in range(2, sqrt_n + 1): if n % i == 0: #2.如果n不是素数，加入列表 factor_list.append(i) is_prime = get_factor(int(n/i)) #3.进入递归循环，直至新产生的n为素数为止 break if is_prime: #4.新的n为素数，递归结束。 factor_list.append(n) return False N = int(input("请输入一个大于1的正整数：")) factor_list = [] get_factor(N) print(f"可分解为{factor_list}")