【ACM算法】-- 数学问题篇 - 分解素因数
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【ACM算法】-- 数学问题篇 - 分解素因数，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2277字，纯文字阅读大概需要4分钟。
内容图文
第一题：
思路：
这个题，虽说看着恶心，但是，这是一个组合类型的题目，相当于一个素数筛法和一个取模运算的综合题。至于计算质因数，只需要一直取模一直取模就可以了，只不过这个代码要和数位拆解的代码进行相应的区分。
代码如下：
#include<stdio.h>
bool mark[100001];
int prime[100001];
int primeSize;
void init(){
for(int i=0;i<100001;i++){
mark[i]=false;
}
primeSize=0;
for(int i=2;i<100001;i++){
if(mark[i]==true)continue;
prime[primeSize++]=i;
if(i>=1000)continue;//对于这个，我个人感觉可加可不加，，
//因为这个语句相对于下面的只是少了一个加减乘除运算的步骤，至于这个时间消耗，可能不是很大吧。
for(int j=i*i;j<100001;j+=i){
mark[j]=true;
}
}
}//素数筛法模板函数
int main(){
init();
int n;
while(scanf("%d",&n)!=EOF){
int ansPrime[30];//记录，结果的素因数
int ansSize=0;//记录结果的个数
int ansNum[30];//记录结果的幂次
for(int i=0;i<primeSize;i++){//对于所有的素数，依次判断是否为因数
if(n%prime[i]==0){
ansPrime[ansSize]=prime[i];
ansNum[ansSize]=0;//如果可以，进行相应的初始化准备工作
while(n%prime[i]==0){
ansNum[ansSize]++;
n/=prime[i];
}
ansSize++;
if(n==1)break;//当n变为1的时候说明素因数已经分解完毕了。
}
}
if(n!=1){//若此时的n不为1，则一定存在一个大于100000的因数，并且这个因数一定为素因数
ansPrime[ansSize]=n;
ansNum[ansSize++]=1;
}
int ans=0;
for(int i=0;i<ansSize;i++){
ans+=ansNum[i];
}
printf("%d\n",ans);
}
return 0;
}
难点：
对于这个，难点可能有三个：
- 为什么只用100000以内的素因数
- 为什么当n=1时，余下的那个数一定是一个素因数。
- 为什么分解素因数要从小开始，难道答案就一定唯一吗？
答：
首先回答第三个问题，这个答案一定是唯一的，证明（个人理解）：
假设答案不唯一，则对于数 n 存在一个结果 : x1*x2*x3=y1*y2*y3，其中x与y不完全相同
因为每个数都是素数，并且是整数，只存在1和其本身为其因数。
假设x3与y不同，这时将x3除过去，如下 x1*x2=y1*y2*y3 / x3 此时x1*x2必为一个整数
那么右边也必然是一个整数，也就是说x3必然被约掉了，即y1*y2*y3这个因式中必然存在因子可以约掉x3，
但是他们都是素数，对于素数来说，只存在1和其本身为其因数，所以原则上他们数不能约分的。
所以这就与假设所矛盾，即上面这种结果根本就不存在，即答案必然唯一。
其次是第一个问题和第二个问题：
现在n可分解素因数，对于其素因数来说，如果存在大于sqrt(n)的因数，只能有一个，如果有俩，就大于n了。
所以我们只需要遍历小于sqrt(n)的素因数，剩下的那一个必然为大于sqrt(n)的，且必然为素因数。
第二题：
内容总结
以上是互联网集市为您收集整理的【ACM算法】-- 数学问题篇 - 分解素因数全部内容，希望文章能够帮你解决【ACM算法】-- 数学问题篇 - 分解素因数所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】