整数因子分解问题（多种方法）

整数因子分解问题
Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description
大于1的正整数n可以分解为：n=x1x2…xm。例如，当n=12 时，共有8 种不同的分解式：
12=12；
12=62；
12=43；
12=34；
12=322；
12=26；
12=232；
12=22*3。
对于给定的正整数n，计算n共有多少种不同的分解式。
Input
输入数据只有一行，有1个正整数n (1≤n≤2000000000)。
Output
将计算出的不同的分解式数输出。
Sample Input
12
Sample Output
8
超时代码

#include
using namespace std;
int f(int n)
{int num=0;for(int i=2; i<n; i++){if(n%i==0){num++;num+=f(n/i);}}return num;
}
int main()
{int n;cin>>n;cout<<f(n)+1<<endl;return 0;
}

AC代码
通过以上代码学习到这样一个事实，若一个整数n有一个大于sqrt(n)的因子，则n的其他因子必然小于sqrt(n)，且大于sqrt(n)的因子最多只有一个。(惭愧。。这么明显的问题，没有想到过)。因此，上面的代码在查找数n的因子时，只需循环到sqrt(n)就可以。并且，这个大于sqrt(n)的因子必然是一个质数，或者为1，所以最后再乘一个m。

#includeusing namespace std;int n;
int sum = 1;
void solve(int n)
{///若一个整数n有一个大于sqrt(n)的因子，///则n的其他因子必然小于sqrt(n)，///且大于sqrt(n)的因子最多只有一个。for(int i = 2; i <= sqrt(n); i++){if(n % i == 0){solve(i);if(i * i != n)///2个数不同交换位置就2种，+2{sum += 2;solve(n / i);}else          ///两数相同，没有先后区别，+1；sum++;}}
}
int main()
{cin>>n;solve(n);cout<<sum;return 0;
}/***************************************************
User name:
Result: Accepted
Take time: 308ms
Take Memory: 192KB
Submit time: 2019-09-09 14:40:02
****************************************************/

最后还有一个时间更短的代码
使用一个map型的数组a,将每个数的因式分解存在对应的map下,例如map<6,4>表示6的因式分解次数是4次，所以，map中n中的数即为结果；(看别人的，不知道对不对，自行测试）

    #includeusing namespace std;map<int, int> a;int f(int n){if(n == 1){return 1;}if(a[n]){return a[n];}int count = 1;for(int i = 2;i<=sqrt(n);i++){if(n%i == 0){count+=f(i);if(i!=n/i){count+=f(n/i);}}}a[n] = count;return count;}int main(){int n;scanf("%d",&n);printf("%d\n",f(n));}/***************************************************User name: Result: AcceptedTake time: 8msTake Memory: 184KBSubmit time: 2019-09-09 10:46:52****************************************************/

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！