求N所有正约数

题意：给定一个正整数N（N < 2*10e9），求N所有正约数。

解题思路：10e9之内约数个数最多的数的约数个数为1536个。我们可以计算根号N的所有质数，进而求出其约数。

代码实例：

复制代码//唯一分解定理 //前10000个数中有1229个素数 //10e9自然数内，约数最多的数的约数个数为1536 //我们只能算到2*10e5 #include<iostream> #include<cstring> #include<cmath> using namespace std; const int maxn = 2*100000; int e[20]; int primes[20]; bool isPrime[maxn]; int ans = 1; int cnt = 0; int k = 0; void dfs(int pos){ k++; if(pos == cnt){ cout << ans << endl; return ; } for(int i = 0;i <= e[pos];i++){ ans *= pow(primes[pos],i); dfs(pos+1); ans /= pow(primes[pos],i); } } int main(){ memset(isPrime,true,sizeof isPrime); int m = sqrt(m); for(int i = 2;i < m;i++){ if(isPrime[i]) for(int j = i*i;j < maxn ;j += i) isPrime[j] = false; } int n; cin >> n; for(int i = 2;i < n;i++) if(isPrime[i]){ if(n%i == 0) primes[cnt++] = i; } for(int i = 0;i < cnt;i++){ while(n%primes[i] == 0){ e[i]++; n/=primes[i]; } } dfs(0); cout << "k = " << k << endl; for(int i = 0;i < cnt;i++) cout << primes[i] << " "; return 0; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//唯一分解定理
//前10000个数中有1229个素数 
//10e9自然数内，约数最多的数的约数个数为1536 
//我们只能算到2*10e5 
#include<iostream>
#include<cstring> 
#include<cmath>
using namespace std;
const int maxn = 2*100000;
int e[20];
int primes[20];
bool isPrime[maxn];
int ans = 1;
int cnt = 0;
int k = 0;
void dfs(int pos){
	k++;
	if(pos == cnt){
		cout << ans << endl;
		return ;
	}
	for(int i = 0;i <= e[pos];i++){
		ans *= pow(primes[pos],i);
		dfs(pos+1);
		ans /= pow(primes[pos],i);
	}
} 
int main(){
	memset(isPrime,true,sizeof isPrime);
	int m = sqrt(m);
	for(int i = 2;i < m;i++){
		if(isPrime[i])
		for(int j = i*i;j < maxn ;j += i)
			isPrime[j] = false;
	}
	int n;
	cin >> n;
	for(int i = 2;i < n;i++) if(isPrime[i]){
		if(n%i == 0)	primes[cnt++] = i;
	}
	for(int i = 0;i < cnt;i++){
		while(n%primes[i] == 0){
			e[i]++;
			n/=primes[i];
		}
	}
	dfs(0);
	cout << "k = " << k << endl;
		for(int i = 0;i < cnt;i++)	cout << primes[i] << " ";
	return 0;
}