首页 > 其他 > 详细

唯一分解定理

时间:2020-06-29 23:03:14      阅读:61      评论:0      收藏:0      [点我收藏+]

唯一分解定理:

定义:对于任意一个大于1的自然数,必定能以质数的连续乘积的形式来表达。(个人口述,非标准,但足够易懂)

关于唯一分解定理的证明
设当前数字为a.
· 假如a是一个质数:那没什么好说的,a的因数只有1和a,则a就应该用其自身表示。
· 假如a是一个合数:那么根据合数的定义,a一定可以分解为几个数字的乘积的形式。那么递归地考虑,只要是一个合数就可以继续分解,而当分解到了质数就无法继续分解下去,因此所有的质数最终都可以由质数的乘积来表示。

使用时的小技巧:
还是,假设当前要分解的数字为a
当分解a的数字处于sqrt(a)~a时,这种数字只可能在一个位置出现一次。理由也很简单,当sqrt(a)*sqrt(a)时,就已经等于a,所有两个大于sqrt(a)的数字的乘积必定会大于a。
因此,假如要分解一个很大的数字(n),那么筛质数和分解的过程可以只求到sqrt(n)即可,倘若完成之后n仍然大于1,那么n的值就是n大于sqrt(n)的“唯一的”质因数。

唯一分解定理

原文:https://www.cnblogs.com/ticmis/p/13210786.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!