C++程序 找到一个自然数的所有因子
给定一个自然数n,输出它的所有不同的因子。
举个例子:
输入: n = 10
输出: 1 2 5 10
输入: n = 100
输出: 1 2 4 5 10 20 25 50 100
输入: n = 125
输出: 1 5 25 125
请注意,此问题与“找到所有质因数”不同。
试一下!
一个 Naive Solution(朴素的解法) 就是迭代1到n的所有数字,判断它是否能够整除n,并输出。以下是相同的程序:
输出:
时间复杂度: O(n)
辅助空间: O(1)
我们能否改进上面的解法?
如果我们仔细观察,所有的因子都成对存在。例如,如果n = 100,则各种因子对为:(1,100),(2,50),(4,25),(5,20),(10,10)
利用这一事实,我们可以显著加快程序。
然而,如果存在两个相等的因子(例如(10,10)的情况),我们必须小心。在这种情况下,我们只会输出一个。
以下是实现的代码:
输出:
时间复杂度:O(sqrt(n))
辅助空间:O(1)