43.质因数分解

题目链接

1.5编程基础之循环控制_43:质因数分解

题解

n = a * b

a、b均为质数.

所以为了我们这个程序的速度更优秀.

我们枚举2-n之间的所有数字.(其实只用到sqrt(n)就好了)

一旦除尽了.说明找到了第一个能整除ab的整数.(按照题目说的,这个数字是质数)

那么可以发现,我们先找到的数字一定是较小的数字.

可以用反证法证明.

假设先找到的数字是较大的数字.当前数字为k

那么2-k一定全部都枚举判断过.

那么另外一个数字较小为l

可知l一定在区间2-k之间.

然而2-k之间一定全都枚举过了.

所以一定是l先出现.

证毕.


By:Wahacer

2017.11.24

23:24

发表评论

电子邮件地址不会被公开。 必填项已用*标注