请教KeyTo9大神一个关于分解质因数的问题【keyto9吧】

keyto9吧关注：538贴子：7,724

@KeyTo9

送TA礼物

IP属地:山东

1楼2017-05-27 19:49回复

是如何不用引入素数表，也不需要素性判断的？

IP属地:山东

2楼2017-05-27 19:50

仔细一想从2到Sqrt(n)一个个除上去似乎也能满足要求？？

IP属地:山东

3楼2017-05-27 19:52

不妨n为奇数。
依次测试奇数3,5,7..能否整除n，
若遇到奇因子k，就让n不断除以k直到除不尽为止
这里n是一个变量，随程序运行可能变小，当被测试的奇数＞n时停止程序

IP属地:北京

来自手机贴吧4楼2017-05-27 20:16

收起回复

可以肯定若k|n，则k一定是素数。举个例好说明
比如，有可能k=35时才遇到k|n吗？不可能的, 因为k=5时早已能k|n，之后n的因子5已经除光了，后面不能再遇着35|n

IP属地:北京

来自手机贴吧5楼2017-05-27 20:19

下载贴吧APP
看高清直播、视频！

贴吧热议榜

发表回复

内容:

使用签名档查看全部

发表

保存至快速回贴