快捷搜索:  汽车  科技

1为什么不是质数?质数为什么不包含1

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

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

1为什么不是质数?质数为什么不包含1(1)

目录

往期回顾

01 余数

02 约数与倍数

03 质数

正文第4节 质因数分解

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

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

1为什么不是质数?质数为什么不包含1(2)

质数还能再分吗?如果将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}")

猜您喜欢: