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，并输出。以下是相同的程序：

// C++ implementation of Naive 
// method to print all divisors
#include <iostream>
using namespace std;
  
// Function to print the divisors
void printDivisors(int n)
{
    for (int i = 1; i <= n; i++)
        if (n % i == 0)
            cout <<" " << i;
}
  
// Driver code
int main()
{
    cout <<"The divisors of 100 are: ";
    printDivisors(100);
    return 0;
}
  
// This code is contributed by shivanisinghss2110```  

输出：

The divisors of 100 are: 
1 2 4 5 10 20 25 50 100

时间复杂度: O(n)

辅助空间: O(1)

我们能否改进上面的解法？

如果我们仔细观察，所有的因子都成对存在。例如，如果n = 100，则各种因子对为：(1,100)，(2,50)，(4,25)，(5,20)，(10,10)

利用这一事实，我们可以显著加快程序。

然而，如果存在两个相等的因子（例如（10,10）的情况），我们必须小心。在这种情况下，我们只会输出一个。

以下是实现的代码：

// A Better (than Naive) Solution 
// to find all divisors
#include <iostream>
#include <math.h>
using namespace std;
  
// Function to print the divisors
void printDivisors(int n)
{
    // Note that this loop runs 
    // till square root
    for (int i = 1; i <= sqrt(n); i++)
    {
        if (n % i == 0)
        {
            // If divisors are equal, 
            // print only one
            if (n / i == i)
                cout <<" "<< i;
  
            // Otherwise print both
            else 
                cout << " "<< i << " " << n / i;
        }
    }
}
  
// Driver code
int main()
{
    cout <<"The divisors of 100 are: ";
    printDivisors(100);
    return 0;
}
  
// This code is contributed by shivanisinghss2110```  

输出：

The divisors of 100 are: 
1 100 2 50 4 25 5 20 10

时间复杂度：O(sqrt(n))

辅助空间：O(1)