当前位置:首页 > 数论 > 正文
SSOJ2662正整数的唯一分解定理
112+

题目大意:将一个大于1的自然数进行质因数分解,以“n=质因子乘积”的形式输出来。

题目描述

算术基本定理,又称为正整数的唯一分解定理,即:每个大于1的自然数均可写为质数的积,而且这些素因子按大小排列之后,写法仅有一种方式。

先给出一个大于1的自然数,请将其写成质因数乘积的形式,如:

6=2*3

12=2*2*3

25=5*5

37=37

……

输入

输入一个大于1的自然数

输出

输出质因数分解等式

样例输入

12345

样例输出

12345=3*5*823

解题思路

对于大于1的自然数n,其质因子从小打到可能是2、3、5、7……

我们可以从小到大枚举因子,发现一个因子i,就除以i,除到不能整除i为止,这样n就少了一种因子了。

如果这个因子是2,那么n除以多次2之后,后面就不会在找到4这种合数因子了。

因此,后面继续这样找因子,找到的都是质因子,不可能是合数因子:如果有合数因子,合数可以质因数分解,说明存在更小的因子,与从小到大枚举因子相矛盾。

最后需要注意的是,一个数的因子,一半小于等于√n,另外一半大于等于√n,为避免超时,我们只需要枚举前面小的一半;这样的话,可能会漏掉一个大的质因子,如21=3*7,i只会枚举到√21=4,7就不会枚举了;因此,如果最后n还大于1,那么剩下的n不能再分解必是一个较大的质因子。

时间复杂度是O(√n),虽然是嵌套循环,但内重循环只会让外重循环更快介绍,循环次数并不是乘积的关系。

程序实现

更多

About

坚决不Copy代码!

本文标签:,,,,,

SSOJ2662正整数的唯一分解定理:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter