有效地获得给定数字的所有除数

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. 获得这些素因子的所有可能组合.

但是,它似乎不是一个好的.

Answer 1

因素是配对的.1和24,2和12,3和8,4和6.

您的算法的改进可能是迭代到平方根num而不是一直到num,然后使用计算成对因子num / i.

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';
}

Answer 3

目前在科学中已知的算法复杂度(具有多项式复杂度的算法)意义上没有有效的方法.因此,如已经建议的那样迭代直到平方根最为可能.

主要是因为这一点,目前使用的密码术的很大一部分是基于这样的假设,即计算任何给定整数的素因数分解是非常耗时的.

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)作为输入,找出其素因子和相应的指数,并将它们放在向量因子[]中.例如,primeFactors(12)将以这种方式填充因子[]:

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

如12 = 2 ^ 2*3 ^ 1

第三部分setDivisors()以递归方式调用自身来计算x的所有除数,使用向量因子[]并将它们放在向量除数[]中.

它可以计算任何适合int的数的除数.它也很快.

Answer 5

找到所有不太大数的主要因素存在很多好的解决方案.我只想指出,一旦你拥有它们,就不需要计算来获得所有因素.

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

因此,因子的数量很明显,(a+1)(b+1)(c+1)....因为每个因素都可以达到零次.

例如12 = 2^2*3^1,它有3*2 = 6因素.1,2,3,4,6,12

======

我原本以为你只想要不同因素的数量.但同样的逻辑适用.您只需迭代与指数的可能组合相对应的数字集.

以上是他的例子:

00
01
10
11
20
21

给你的6因素.