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

Question

根据此post，我们可以通过以下代码获取数字的所有除数。

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

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

在搜索了一些相关文章后，我没有找到任何好的解决方案。有没有什么有效的方法来完成这个？

我的解决办法：

1. 通过这个solution查找给定数的所有素因子。
2. 获取这些主要因素的所有可能组合。

但是，它似乎不是一个好的。

Answer 1

因素配对。 1和24,2和12,3和8,4和6。

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

Answer 2

你真的应该检查，直到NUM的平方根（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

有很多很好的解决方案可以找到所有不太多的主要因素。我只想指出，一旦你拥有了它们，就不需要计算来获得所有的因素。

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

接着的因素的数量显然(a+1)(b+1)(c+1)....因为每个因子可以orruc零到一次。

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

======

我原本以为你只是想的不同因素的数量。但是同样的逻辑适用。您只需遍历与可能的指数组合对应的数字集。

这样诠释他上面的例子：

00 
01 
10 
11 
20 
21 

给你6因素。

Answer 5

这里是我的代码：

#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(); 
    } 
} 

第一部分，筛（）是用来寻找素数，并把他们的素数[]数组。按照链接查找有关该代码的更多信息（按位筛选）。

第二部分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 6

for(int i = 1; i * i <= num; i++) {/ * upto sqrt是因为sqrt后面的所有数字也会在数字被i分隔时找到。例如，如果数字是90时除以5，那么你也可以看到90/5 = 18，其中18也除以数字 ，但是当数字是完美的正方形，那么num/i == i因此只有i是因数*/

Answer 7

我们也可以指的是使用素数因子在许多例如:::

 100  
    /\ 
    10 10 
/\/\ 
    2 5 5 2 

因而我们有（2^2）（5^2）从这里，我们将添加的每个1到2和5的权力。现在我们有3 * 3 = 9的因子总数为100（即1,2,4,5,10,20,25,50,100） 因此，我们可以使用这种方法来查找非常大的因子和最终减少迭代的次数。

Answer 8

//Try this,it can find divisors of verrrrrrrrrry big numbers (pretty efficiently :-)) 
#include<iostream> 
#include<cstdio> 
#include<cmath> 
#include<vector> 
#include<conio.h> 

using namespace std; 

vector<double> D; 

void divs(double N); 
double mod(double &n1, double &n2); 
void push(double N); 
void show(); 

int main() 
{ 
    double N; 
    cout << "\n Enter number: "; cin >> N; 

    divs(N); // find and push divisors to D 

    cout << "\n Divisors of "<<N<<": "; show(); // show contents of D (all divisors of N) 

_getch(); // used visual studio, if it isn't supported replace it by "getch();" 
return(0); 
} 

void divs(double N) 
{ 
    for (double i = 1; i <= sqrt(N); ++i) 
    { 
     if (!mod(N, i)) { push(i); if(i*i!=N) push(N/i); } 
    } 
} 

double mod(double &n1, double &n2) 
{ 
    return(((n1/n2)-floor(n1/n2))*n2); 
} 

void push(double N) 
{ 
    double s = 1, e = D.size(), m = floor((s + e)/2); 
    while (s <= e) 
    { 
     if (N==D[m-1]) { return; } 
     else if (N > D[m-1]) { s = m + 1; } 
     else { e = m - 1; } 
     m = floor((s + e)/2); 
    } 
    D.insert(D.begin() + m, N); 
} 

void show() 
{ 
    for (double i = 0; i < D.size(); ++i) cout << D[i] << " "; 
} 

Answer 9

int result_num; 
bool flag; 

cout << "Number   Divisors\n"; 

for (int number = 1; number <= 35; number++) 
{ 
    flag = false; 
    cout << setw(3) << number << setw(14); 

    for (int i = 1; i <= number; i++) 
    { 
     result_num = number % i; 

     if (result_num == 0 && flag == true) 
     { 
      cout << "," << i; 
     } 

     if (result_num == 0 && flag == false) 
     { 
      cout << i; 
     } 

     flag = true; 
    } 

    cout << endl; 
} 
cout << "Press enter to continue....."; 
cin.ignore(); 
return 0; 
} 

Answer 10

我做了一个更简单的概念，但仍然工作正常

enter code here 
#include <iostream> 
#include <stdio.h> 
#include <math.h> 

bool loop = true; 
int x,y,z=1; 
using namespace std; 

void menu(){ 
cout << "\n Inserisci il numero da anaizzare : "; #it insetrs the number 
that will be analised 
cin >> x; 
} 
void algoritmo(){ 
for (int y=1;y<=x;y++){ 
    if (x%y!=0){ 
     y++; 
    } 
    else{ 
     cout << " " << y; 
    } 
} 
} 

int main(){ 
while (loop == true){ 
    menu(); #this is the void for the menu 
    algoritmo(); #this is the void the algorithm 
} 
return 0; 
}