1为什么不是质数?质数为什么不包含1
1为什么不是质数?质数为什么不包含1题1 直接分解在很久以前,1确实被看成一个素数。比如大数学家欧拉就在给朋友的信件中写道:除1外所有的素数……现在数学在定义上认为1既不是素数也不是合数。有个问题,素数不包含1,合数也不包含1,1招谁惹谁了?为什么阳间不要,阴间不收呢?这个问题可以用质因数分解来解答。所谓质因数,其实就是任何一个除1外的正整数,它能分解成所有质数的乘积,如100=2×2×5×5——所有的因子都是质数。质数还能再分吗?如果将2再分成1×2,那么就还能继续分下去,就成了一个死循环。
本文节选自《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}")