问题描述：
大于1 的正整数n 可以分解为：n=x1*x2*…*xm。
例如，当n=12 时，共有8 种不同的分解式：
12=12；
12=6*2；
12=4*3；
12=3*4；
12=3*2*2；
12=2*6；
12=2*3*2；
12=2*2*3 。
编程任务：
对于给定的正整数n，编程计算n 共有多少种不同的分解式。
数据输入：
由文件input.txt 给出输入数据。第一行有1 个正整数n (1≤n≤2000000000)。
结果输出:
将计算出的不同的分解式数输出到文件output.txt 。
输入文件示例 输出文件示例
input.txt output.txt
12 8
本题使用到了分治法和欧拉线性筛法来求解
欧拉线性筛法时间复杂度为O(n):
参考到这篇博客:文章来源：https://www.toymoban.com/news/detail-795745.html
初等数论1（对应基础课数学知识第一堂课） - AcWing文章来源地址https://www.toymoban.com/news/detail-795745.html
#include<iostream>
using namespace std;
const int N=100010;
int n,cnt;
bool st[N];
int prime[N];
void getPrime(int n)
{
for (int i = 2; i <= n; i++) {
if (!st[i]) prime[cnt++] = i;
for (int j = 0; i * prime[j] <= n; j++) {
st[i * prime[j]] = true;
if (i % prime[j] == 0) break;
}
}
}
int solve(int n)
{
int k=1;//分解式数量
// printf("进入:solve(%d),k=%d\n",n,k);
if(!st[n]) return 1;
for(int i=n-1;i>=2;i--)
{
if(n%i==0) k+=solve(i);
}
// printf("退出:solve(%d),k=%d\n",n,k);
return k;
}
int main()
{
cin>>n;
getPrime(N);
int t=solve(n);
printf("%d",t);
return 0;
}到了这里，关于整数因子分解问题(分治法&&欧拉线性筛素数)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
