C++ 有效地获得给定数字的所有除数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/26753839/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Efficiently getting all divisors of a given number
提问by zangw
According to this post, we can get all divisors of a number through the following codes.
根据这篇文章，我们可以通过以下代码获得一个数字的所有除数。
for (int i = 1; i <= num; ++i){
if (num % i == 0)
cout << i << endl;
}
For example, the divisors of number 24are 1 2 3 4 6 8 12 24.
例如，number 的除数24是1 2 3 4 6 8 12 24。
After searching some related posts, I did not find any good solutions. Is there any efficient way to accomplish this?
搜索了一些相关的帖子，没有找到好的解决办法。有没有什么有效的方法来实现这一点？
My solution:
我的解决方案：
- Find all prime factors of the given number through this solution.
- Get all possible combinations of those prime factors.
- 通过此解找出给定数的所有质因数。
- 获取这些主要因素的所有可能组合。
However, it doesn't seem to be a good one.
然而，它似乎不是一个好方法。
回答by Yu Hao
Factors are paired. 1and 24, 2and 12, 3and 8, 4and 6.
因素是成对的。1和24、2和12、3和8、4和6。
An improvement of your algorithm could be to iterate to the square root of numinstead of all the way to num, and then calculate the paired factors using num / i.
算法的改进可能是迭代到 的平方根num而不是一直到num，然后使用 计算配对因子num / i。
回答by SMA
You should really check till square root of num as sqrt(num) * sqrt(num) = num:
你真的应该检查直到 num 的平方根为 sqrt(num) * sqrt(num) = num：
Something on these lines:
这些线路上的东西：
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';
}
回答by SpaceTrucker
There is no efficient way in the sense of algorithmic complexity (an algorithm with polynomial complexity) known in science by now. So iterating until the square root as already suggested is mostly as good as you can be.
目前在科学上已知的算法复杂度（具有多项式复杂度的算法）意义上没有有效的方法。因此，迭代直到已经建议的平方根大部分都尽可能好。
Mainly because of this, a large part of the currently used cryptography is based on the assumption that it is very time consuming to compute a prime factorization of any given integer.
主要是因为这个，目前使用的密码学的很大一部分是基于这样的假设，即计算任何给定整数的质因数分解是非常耗时的。
回答by Rocky Johnson
Here's my code:
这是我的代码：
#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();
}
}
The first part, sieve() is used to find the prime numbers and put them in primes[] array. Follow the link to find more about that code (bitwise sieve).
第一部分，sieve() 用于查找素数并将它们放入 primes[] 数组中。按照链接查找有关该代码的更多信息（按位筛分）。
The second part primeFactors(x) takes an integer (x) as input and finds out its prime factors and corresponding exponent, and puts them in vector factors[]. For example, primeFactors(12) will populate factors[] in this way:
第二部分 primeFactors(x) 以整数 (x) 作为输入，找出它的素因子和对应的指数，并将它们放入向量 factor[] 中。例如， primeFactors(12) 将以这种方式填充 factor[]：
factors[0].first=2, factors[0].second=2
factors[1].first=3, factors[1].second=1
as 12 = 2^2 * 3^1
因为 12 = 2^2 * 3^1
The third part setDivisors() recursively calls itself to calculate all the divisors of x, using the vector factors[] and puts them in vector divisors[].
第三部分 setDivisors() 递归调用自身来计算 x 的所有除数，使用向量 factor[] 并将它们放入向量 divisors[] 中。
It can calculate divisors of any number which fits in int. Also it is quite fast.
它可以计算适合 int 的任何数字的除数。它也非常快。
回答by phil_20686
Plenty of good solutions exist for finding all the prime factors of not too large numbers. I just wanted to point out, that once you have them, no computation is required to get all the factors.
有很多很好的解决方案可以找到不是太大的数的所有质因数。我只是想指出，一旦你有了它们，就不需要计算来获得所有的因素。
if N = p_1^{a}*p_{2}^{b}*p_{3}^{c}.....
如果 N = p_1^{a}*p_{2}^{b}*p_{3}^{c}.....
Then the number of factors is clearly (a+1)(b+1)(c+1)....since every factor can occur zeroup to atimes.
那么因子的数量很明显，(a+1)(b+1)(c+1)....因为每个因子都可以出现零次，最多一次。
e.g. 12 = 2^2*3^1so it has 3*2 = 6factors. 1,2,3,4,6,12
例如12 = 2^2*3^1所以它有3*2 = 6因素。1,2,3,4,6,12
======
======
I originally thought that you just wanted the number of distinct factors. But the same logic applies. You just iterate over the set of numbers corresponding to the possible combinations of exponents.
我最初认为您只想要不同因素的数量。但同样的逻辑也适用。您只需遍历与可能的指数组合相对应的一组数字。
so int he example above:
所以在上面的例子中：
00
01
10
11
20
21
gives you the 6factors.
给你6因素。
回答by Pratik Patil
Here is the Java Implementation of thisapproach:
这是这种方法的 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();
}
回答by Sifat Ullah Chowdhury
for (int i = 1; i*i <= num; ++i)
{
if (num % i == 0)
cout << i << endl;
if (num/i!=i)
cout << num/i << endl;
}
回答by Aditya
//DIVISORS IN TIME COMPLEXITY sqrt(n)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ll int n;
cin >> n;
for(ll i = 2; i <= sqrt(n); i++)
{
if (n%i==0)
{
if (n/i!=i)
cout << i << endl << n/i<< endl;
else
cout << i << endl;
}
}
}
回答by Apoorva Raj Bhadani
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define MOD 1000000007
#define fo(i,k,n) for(int i=k;i<=n;++i)
#define endl '\n'
ll etf[1000001];
ll spf[1000001];
void sieve(){
ll i,j;
for(i=0;i<=1000000;i++) {etf[i]=i;spf[i]=i;}
for(i=2;i<=1000000;i++){
if(etf[i]==i){
for(j=i;j<=1000000;j+=i){
etf[j]/=i;
etf[j]*=(i-1);
if(spf[j]==j)spf[j]=i;
}
}
}
}
void primefacto(ll n,vector<pair<ll,ll>>& vec){
ll lastprime = 1,k=0;
while(n>1){
if(lastprime!=spf[n])vec.push_back(make_pair(spf[n],0));
vec[vec.size()-1].second++;
lastprime=spf[n];
n/=spf[n];
}
}
void divisors(vector<pair<ll,ll>>& vec,ll idx,vector<ll>& divs,ll num){
if(idx==vec.size()){
divs.push_back(num);
return;
}
for(ll i=0;i<=vec[idx].second;i++){
divisors(vec,idx+1,divs,num*pow(vec[idx].first,i));
}
}
void solve(){
ll n;
cin>>n;
vector<pair<ll,ll>> vec;
primefacto(n,vec);
vector<ll> divs;
divisors(vec,0,divs,1);
for(auto it=divs.begin();it!=divs.end();it++){
cout<<*it<<endl;
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
sieve();
ll t;cin>>t;
while(t--) solve();
return 0;
}
回答by Ragib
//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] << " ";
}
