先附上所有因数的求法：
我的做法：是今天误打误撞写出来的；
http://exam.upc.edu.cn/problem.php?id=5062
然后，我上网找居然没有人写一个高效一点的，我这个做法其实就是.
不一定要会比根号N快，但是
模拟求所有因子个数的做法：
大家知道为什么所有因子的个数为：
设P1，P2……Pn都是数的质因子，
设C1，C2……Cn是数的质因子的个数：
Ans=（C1+1）*（C2+1）*……*（Cn+1）
大家想知道模拟一下就知道为什么了。
比如120=2*2*2*3*5；
那么Ans=（3+1）*（1+1）*（1+1）
要是求它的因子那么就是：
（1+2+4+8）*（1+3）*（1+5）
=（1+2+4+8）+（3+6+12+24）+（5+10+20+40）+（15+30+60+120）
其中所有因数为：
1 , 2 , 3 , 4 , 5 , 6 , 8 , 10 , 12 , 15 , 20 , 24 , 30 , 40 , 60 , 120
因数之和就是
=（1+2+4+8）+（3+6+12+24）+（5+10+20+40）+（15+30+60+120）
大家琢磨琢磨为什么是这样。
#include<bits/stdc++.h>
using namespace std;
const int N=5e6+10;
typedef long long ll;
ll qpow(ll a,ll b){
ll ans=1;
while(b){
if(b&1){
ans=ans*a;
}
a=a*a;
b>>=1;
}
return ans;
}
/*
(2*3*5*7*11)*(13*17*19*23*29)*(31*37*41*43*47)
=614,88978,25884,91410
前15个质数相乘得到一个 6 e18的数字
*/
vector<ll>v[20];
map<ll,int>Vis;
ll a[N],cnt,Type;
void dfs(ll x,int step){
if(Vis[x]==0&&step==Type){
Vis[x]=1;
a[cnt++]=x;
return ;
}
for(int i=0;i<v[step].size();i++){
dfs(x*v[step][i],step+1);
}
}
void solve(){
ll n;
scanf("%lld",&n);
cnt=0;
for(int i=0;i<20;i++){
v[i].clear();
}
Type=0;
Vis.clear();
for(ll i=2;i*i<=n;i++){
if(n%i==0){
int D=0;
while(n%i==0){
D++;
n/=i;
}
for(int j=0;j<=D;j++){
v[Type].push_back(qpow(i,j));
}
Type++;
}
}
if(n!=1){
v[Type].push_back(1);
v[Type].push_back(n);
Type++;
}
dfs(1,0);
sort(a,a+cnt);
for(int i=0;i<cnt;i++){
printf("%lld%c",a[i],i==cnt-1?'\n':' ');
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--){
solve();
}
return 0;
}
归纳总结一下：质因数分解更快的做法：
1589: 题目名称:分解质因数
时间限制: 1 Sec 内存限制: 128 MB
题目描述
求出区间[a,b]中所有整数的质因数分解。
输入
输入两个整数a，b。
输出
每行输出一个数的分解，形如k=a1*a2*a3...(a1<=a2<=a3...，k也是从小到大的)(具体可看样例)
样例输入
3 10
样例输出
3=3
4=2*2
5=5
6=2*3
7=7
8=2*2*2
9=3*3
10=2*5
提示
先筛出所有素数，然后再分解。
数据规模和约定
2<=a<=b<=10000
#include<bits/stdc++.h>
using namespace std;
const int N=100;
typedef long long ll;
ll a[N],cnt;
void solve(ll n){
ll tn=n;
cnt=0;
for(ll i=2;i*i<=n;i++){
if(n%i==0){
int D=0;
while(n%i==0){
D++;
n/=i;
a[cnt++]=i;
}
}
}
if(n!=1){
a[cnt++]=n;
}
sort(a,a+cnt);
printf("%lld=",tn);
for(int i=0;i<cnt;i++){
printf("%lld%c",a[i],i==cnt-1?'\n':'*');
}
}
int main()
{
ll n,m;
scanf("%lld%lld",&n,&m);
for(ll i=n;i<=m;i++){
solve(i);
}
return 0;
}
转载自原文链接, 如需删除请联系管理员。
原文链接：求一个数的所有因数+质因数分解【数论】，转载请注明来源！