有效地获得给定数量的所有因数
根据这个post ，我们可以通过下面的代码得到一个数字的所有因数。
for (int i = 1; i <= num; ++i){ if (num % i == 0) cout << i << endl; } 例如， 24号的除数是1 2 3 4 6 8 12 24 。
在search了一些相关的post后，我没有find任何好的解决scheme。 有没有什么有效的方法来完成这个？
我的解决scheme
- 通过这个解决scheme找出给定数字的所有主要因素。
- 获取这些主要因素的所有可能的组合。
但是，这似乎不是一个好的。
因素配对。 1和24和12和8和6 。
algorithm的一个改进可能是迭代到num平方根，而不是一直到num ，然后使用num / i计算配对因子。
你应该检查，直到平方根为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'; }
目前在科学中已知的algorithm复杂性（一种具有多项式复杂性的algorithm）没有有效的方法。 所以迭代，直到已经build议的平方根大部分是你可以。
主要是因为这个原因，目前使用的密码学的很大一部分是基于这样的假设，即计算任何给定整数的素数分解是非常耗时的。
存在很多好的解决scheme来find所有不太多的主要因素。 我只想指出，一旦有了它们，就不需要计算就可以得到所有的因素。
如果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因素。
这是我的代码：
#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（）用于查找素数并将它们放在素数[]数组中。 按照链接查找有关该代码（按位筛）的更多信息。
第二部分primeFactors（x）以一个整数（x）为input，找出它的素因子和相应的指数，并把它们放在vector因子[]中。 例如，primeFactors（12）将以这种方式填充因子[]：
factors[0].first=2, factors[0].second=2 factors[1].first=3, factors[1].second=1
如12 = 2 ^ 2 * 3 ^ 1
第三部分setDivisors（）recursion地调用它自己来计算x的所有除数，使用vector因子[]并将它们放入vector除数[]中。
它可以计算任何适合int的数的除数。 也是相当快的。
//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] << " "; }
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; }
我们也可以参考使用数字中的素数因子例如:::
100 / \ 10 10 / \ / \ 2 5 5 2
因此我们有（2 ^ 2）（5 ^ 2）从这里我们将加2和5的权力。 现在我们有3 * 3 = 9的因子总数为100（即1,2,4,5,10,20,25,50,100）因此，我们可以使用这种方法来find非常大数量的因素减less迭代的次数。
for( int i = 1; i * i <= num; i++ ) {/ * upto sqrt是因为sqrt后面的所有数字也是在数字被i分割时find的。 例如，如果数字是90时除以5，那么你也可以看到，90/5 = 18其中18也划分数字，但是当数字是完美的正方形，然后num / i ==我只因此我只是因素* /
