高效地获取给定数字的所有因数

Question

根据这个帖子，我们可以通过以下代码获取一个数字的所有因数。

for (int i = 1; i <= num; ++i){
    if (num % i == 0)
        cout << i << endl;
}

例如，数字24的因数是1 2 3 4 6 8 12 24。

在搜索相关帖子后，我没有找到任何好的解决方法。有没有有效的方法来完成这个问题？

我的解决方案：

1.通过此解决方案找到给定数字的所有质因数。 2.获取这些质因数的所有可能组合。

然而，这似乎不是一个好的解决方案。

- zangw

---

你的质数算法方案有什么"不好"的地方？就我个人而言，它似乎是处理大数字最可行的方法。分解因数被认为是一个“困难”（即缓慢）的问题。世界上很多事情都依赖于这一点。你知道预期输入的最大大小吗？一个不那么通用的方法是预先计算适合输入范围的质数表，并使用它。 - BoBTFish

我认为“获取这些质因数的所有可能组合”不可能是高效的。 - zangw

通常情况下，仅获取质因数然后生成组合可能更好。 如果原始数字是质数，则无济于事，但如果不是，则将执行较少的除法运算。 - harold

如果输入非常大，最好先通过质数检查运行它（例如使用Google Rabin-Miller算法）。但是这可能对您正在进行的范围来说有些过度。 - BoBTFish

相比于最初找到质因数，获取所有可能的组合并不高效。哎？与之比较，这基本上只是个计数问题，非常琐碎。 - David Schwartz

Answer 1

因子成对出现，1 和 24，2 和 12，3 和 8，4 和 6。

你的算法可以改进的地方是迭代到平方根num而不是一直到num，然后使用num / i计算成对的因子。

- Yu Hao

---

另外，由于您只关心平方根的整数部分，因此可以使用简单的平方根算法。 - Keen

如果这是一个重复的算法，即想要找出许多数字的因子，可以使用筛法生成所有小于根号n的质数，并生成质因数分解，然后迭代来获取所有的因子，这将会更快。这是因为质数的分布是对数分布的，所以大的质数往往相隔很远。因此你需要做的除法会更少。 - phil_20686

@phil_20686，你提到的是基于动态规划的方法吗？ - taurus05

你也可以通过以下方式节省平方根计算的开销：for (int i = 1; i * i <= num; i++) - Abhishek Choudhary

@l33t 不，这是正确的。按照你的逻辑，它也会错过45。由于9已经被作为除数计算了10次，所以在这种方法中我们必须同时考虑 x 和 num / x。由于 9 * 9 <= 90，我们取 9 和 90/9 = 10。 - Abhishek Choudhary

Answer 2

你应该检查 num 的平方根，因为 sqrt(num) * sqrt(num) = num：

大致如下：

int square_root = (int) sqrt(num) + 1;
for (int i = 1; i < square_root; i++) { 
    if (num % i == 0&&i*i!=num)
        cout << i << num/i << endl;
    if (num % i == 0&&i*i==num)
        cout << i << '\n';
}

- SMA

---

没必要这么做。任何开启优化的 C 编译器都会这样做（例如，Clang 在任何高于 0 的优化级别上都会这样做）。我更担心第一行中的未匹配括号。 - Aaron Dufour

由于 i<square_root，i*i<num，因此无需证明 i*i==num，在 for 循环之后，您应该证明 square_root*square_root==num。 - Juanito Perez

Answer 3

目前科学界尚未找到算法复杂度高效（即多项式时间复杂度）的方法。因此，按照先前建议的迭代到平方根是最好的方法。

主要因为这个原因，当前使用的加密技术很大程度上基于假设计算任何给定整数的质因数分解需要很长时间。

- SpaceTrucker

Answer 4

这是我的代码:

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define pii pair<int, int>

#define MAX 46656
#define LMT 216
#define LEN 4830
#define RNG 100032

unsigned base[MAX / 64], segment[RNG / 64], primes[LEN];

#define sq(x) ((x)*(x))
#define mset(x,v) memset(x,v,sizeof(x))
#define chkC(x,n) (x[n>>6]&(1<<((n>>1)&31)))
#define setC(x,n) (x[n>>6]|=(1<<((n>>1)&31)))

// http://zobayer.blogspot.com/2009/09/segmented-sieve.html
void sieve()
{
    unsigned i, j, k;
    for (i = 3; i<LMT; i += 2)
        if (!chkC(base, i))
            for (j = i*i, k = i << 1; j<MAX; j += k)
                setC(base, j);
    primes[0] = 2;
    for (i = 3, j = 1; i<MAX; i += 2)
        if (!chkC(base, i))
            primes[j++] = i;
}


//http://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/
vector <pii> factors;
void primeFactors(int num)
{
    int expo = 0;   
    for (int i = 0; primes[i] <= sqrt(num); i++)
    {
        expo = 0;
        int prime = primes[i];
        while (num % prime == 0){
            expo++;
            num = num / prime;
        }
        if (expo>0)
            factors.push_back(make_pair(prime, expo));
    }

    if ( num >= 2)
        factors.push_back(make_pair(num, 1));

}

vector <int> divisors;
void setDivisors(int n, int i) {
    int j, x, k;
    for (j = i; j<factors.size(); j++) {
        x = factors[j].first * n;
        for (k = 0; k<factors[j].second; k++) {
            divisors.push_back(x);
            setDivisors(x, j + 1);
            x *= factors[j].first;
        }
    }
}

int main() {

    sieve();
    int n, x, i; 
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x;
        primeFactors(x);
        setDivisors(1, 0);
        divisors.push_back(1);
        sort(divisors.begin(), divisors.end());
        cout << divisors.size() << "\n";
        for (int j = 0; j < divisors.size(); j++) {
            cout << divisors[j] << " "; 
        }
        cout << "\n";
        divisors.clear();
        factors.clear();
    }
}

第一部分sieve()用于查找质数并将它们放入primes[]数组。请点击链接了解有关该代码（位筛法）的更多信息。

第二部分primeFactors(x)接受一个整数（x）作为输入，并找出其质因数及其对应的指数，并将它们放入vector factors[]中。例如，primeFactors(12)将以以下方式填充factors[]：

factors[0].first=2, factors[0].second=2
factors[1].first=3, factors[1].second=1

如 12 = 2^2 * 3^1

第三部分的setDivisors()函数，利用向量factors[]计算x的所有因子并将它们放入向量divisors[]中，通过递归调用自身实现。

它可以计算任何能放在int中的数字的因子，而且速度相当快。

- Rocky Johnson

Answer 5

存在许多很好的解决方案可以找到不太大的数的所有质因子。但我只想指出，一旦你拥有了它们，就不需要进行任何计算即可获得所有的因子。

如果 N = p_1^{a}*p_{2}^{b}*p_{3}^{c}.....

那么因子数量显然为 (a+1)(b+1)(c+1)....，因为每个因子可以出现零次到a次。

例如，12 = 2^2*3^1，因此它有3*2=6个因子。1,2,3,4,6,12

======

我最初认为您只想知道不同因子的数量。但是相同的逻辑也适用。您只需迭代与可能的指数组合相对应的数字集即可。

所以在上面的例子中：

00
01
10
11
20
21

给你 6 个因素。

- phil_20686

---

这是次优的，因为您一遍又一遍地进行相同的乘法运算。 - rwst

Answer 6

如果你想打印出所有的因数并按照顺序排列

int i;
for(i=1;i*i<n;i++){             /*print all the divisors from 1(inclusive) to
    if(n%i==0){                   √n (exclusive) */   
        cout<<i<<" ";
    }
}
for( ;i>=1;i--){                /*print all the divisors from √n(inclusive) to
  if(n%i==0){                     n (inclusive)*/   
      cout<<(n/i)<<" ";
  }
}

如果除数可以以任何顺序打印

for(int j=1;j*j<=n;j++){
    if(n%j==0){
        cout<<j<<" ";
        if(j!=(n/j))
           cout<<(n/j)<<" ";
    }
}

两种方法的复杂度均为O(√n)

- Amisha Sahu

---

我喜欢按升序输出的方法，以及对复杂性的评论。请养成注释和记录代码的习惯：所有东西（外部可见）有什么用处？ - greybeard

非常感谢您的建议，我会记下来的。同时，感谢您为我的解决方案点赞。 - Amisha Sahu

它返回了重复的内容，例如对于数字6，它返回1:2:2:3:6。 - Lance

Answer 7

这里是this方法的Java实现：

public static int countAllFactors(int num)
{
    TreeSet<Integer> tree_set = new TreeSet<Integer>();
    for (int i = 1; i * i <= num; i+=1)
    {
        if (num % i == 0)
        {
            tree_set.add(i);
            tree_set.add(num / i);
        }
    }
    System.out.print(tree_set);
    return tree_set.size();
}

- Pratik Patil

Answer 8

我们可以使用修改后的筛法来获取范围在[1，N-1]内所有数字的因子。

for (int i = 1; i < N; i++) {
    for (int j = i; j < N; j += i) {
        ans[j].push_back(i);
    }
}

时间复杂度为O(N * log(N)) ，因为调和级数的总和1 + 1/2 + 1/3 + ... + 1/N 可以近似为 log(N)。

有关时间复杂度的更多信息：https://math.stackexchange.com/a/3367064 附言：通常在编程问题中，任务将包括多个查询，其中每个查询代表不同的数字，因此预先计算一次范围内所有数字的除数将是有益的，因为在这种情况下查找需要O（1）时间。

- Shreyas Shetty

Answer 9

Java 8 递归（在 HackerRank 上有效）。此方法包括将因子相加并作为整数返回的选项。

    static class Calculator implements AdvancedArithmetic {
        public int divisorSum(int n) {
            if (n == 1)
                return 1;

            Set<Integer> set = new HashSet<>();
            return divisorSum( n, set, 1);
        }

        private int divisorSum(int n, Set<Integer> sum, int start){

            if ( start > n/2 )
                return 0;

            if (n%start == 0)
                sum.add(start);

            start++;

            divisorSum(n, sum, start);

            int total = 0;
            for(int number: sum)
                total+=number;
            return total +n;
        }
    }

- Roberto Cannella

---

实际上，这在大数上不起作用。我将尝试调整算法以包含平方根。 - Roberto Cannella

Answer 10

for( int i = 1; i * i <= num; i++ )
{
/* upto sqrt is because every divisor after sqrt
    is also found when the number is divided by i.
   EXAMPLE like if number is 90 when it is divided by 5
    then you can also see that 90/5 = 18
    where 18 also divides the number.
   But when number is a perfect square
    then num / i == i therefore only i is the factor
*/

- mohit rai

---

这似乎是对问题代码进行改进的建议，而不是完整的解决方案。 - greybeard