唯一分解定理+dfs找因数

唯一分解定理

看这篇博客

dfs找因数

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
const  int N=1e6+131;
ll prime[N];
bool vis[N];
ll a;
int cnt;
void init() {
    for(int i=2;i<=N;i++) {
        if(!vis[i]) {
            prime[cnt++]=i;
        }
        for(int j=0;j<cnt && i*prime[j]<=N;j++) {
            vis[i*prime[j]]=true;
            if(i%prime[j]==0) break;
        }
    }
}
void dfs(int l,ll s) {
    cout<<s<<endl;
    for(int i=l;i<cnt;i++) {
        if(a%(s*prime[i])==0) {
            dfs(i,s*prime[i]);
        }
    }
}
int main() {
    init();
    cin>>a;
    dfs(0,1);
    return 0;
}