算术基本定理,又称为正整数的唯一分解定理,即:每个大于1的自然数均可写为几个质数的积,而且这些质因子按大小排列之后,写法仅有一种方式。
先给出一个大于1的自然数,请将其写成质因数乘积的形式,如:
6=2*3
12=2*2*3
25=5*5
37=37
……
输入输入一个大于1的自然数
输出输出质因数分解等式
样例输入12345
样例输出
12345=3*5*823分析
这道题考察对循环和素数的知识。
循环呢,很简单,不讲。素数呢,可以讲一下。
一个数的因数只有1和自己,那这个数就是素数。想必大家都知道。 这道题呢,要求是“每个大于1的自然数均可写为几个质数的积,而且这些质因子按大小排列之后,写法仅有一种方式”。可能有些人就会先看这个数是不是素数,再去看看能不能整除。
其实没有必要管它是不是素数。因为一个素数不能整除时,那这个素数的倍数就更不可能整除。一个素数能整除时,就除到不能整除为止,那这个素数的倍数就不可能整除了。
#include
using namespace std;
int n,i;
int main(){
scanf("%d",&n);
for(i=2;i<=n;++i) if(n%i==0){
printf("%d=%d",n,i);
n=n/i;
break;
}
for(;i<=n;++i) while(n%i==0){
printf("*%d",i);
n=n/i;
}
return 0;
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)