深入分析C语言分解质因数的实现方法
首先来看一个最简单的C语言实现质因数分解的列子：
#include<stdio.h>
voidmain()
{
intdata,i=2;
scanf("%d",&data);
while(data>1)
{
if(data%i==0)
{
printf("%d",i);
data/=i;
}
elsei++;
}
}
原理&&方法
把一个合数分解为若干个质因数的乘积的形式，即求质因数的过程叫做分解质因数，分解质因数只针对合数
求一个数分解质因数，要从最小的质数除起，一直除到结果为质数为止。分解质因数的算式的叫短除法，和除法的性质差不多，还可以用来求多个个数的公因式：
以24为例：
2--24
2--12
2--6
3（3是质数，结束）
得出24=2×2×2×3=2^3*3
代码
可先用素数筛选法，筛选出符合条件的质因数，然后for循环遍历即可，通过一道题目来show一下这部分代码
题目1
题目描述：
求正整数N(N>1)的质因数的个数。
相同的质因数需要重复计算。如120=2*2*2*3*5，共有5个质因数。
输入：
可能有多组测试数据，每组测试数据的输入是一个正整数N，(1<N<10^9)。
输出：
对于每组数据，输出N的质因数的个数。
样例输入：
120
样例输出：
5
提示：
注意：1不是N的质因数；若N为质数，N是N的质因数。
ac代码
#include<stdio.h>
intmain()
{
intn,count,i;
while(scanf("%d",&n)!=EOF){
count=0;
for(i=2;i*i<=n;i++){
if(n%i==0){
while(n%i==0){
count++;
n/=i;
}
}
}
if(n>1){
count++;
}
printf("%d\n",count);
}
return0;
}
深入理解
我所谓的深入理解，就是通过4星的题目来灵活运用分解质因数的方法，题目如下
题目2
题目描述：
给定n，a求最大的k，使n！可以被a^k整除但不能被a^(k+1)整除。
输入：
两个整数n(2<=n<=1000)，a(2<=a<=1000)
输出：
一个整数.
样例输入：
610
样例输出：
1
思路
a^k和n!都可能非常大，甚至超过longlongint的表示范围，所以也就不能直接用取余操作判断它们之间是否存在整除关系，因此我们需要换一种思路，从分解质因数入手，假设两个数a和b：
a=p1^e1*p2^e2*...*pn^en,b=p1^d1*p2^d2*...*pn^dn
,则b除以a可以表示为：
b/a=(p1^d1*p2^d2*...*pn^dn)/(p1^e1*p2^e2*...*pn^en)
若b能被a整除，则b/a必为整数，且两个素数必护质，则我们可以得出如下规律：
若a存在质因数px，则b必也存在该质因数，且该素因数在b中对应的幂指数必不小于在a中的幂指数
另b=n!,a^k=p1^ke1*p2^ke2*...*pn^ken，因此我们需要确定最大的非负整数k即可。要求得该k，我们只需要依次测试a中每一个素因数，确定b中该素因数是a中该素因数的幂指数的多少倍即可，所有倍数中最小的那个即为我们要求得的k
分析到这里，剩下的工作似乎只是对a和n!分解质因数，但是将n!计算出来再分解质因数，这样n!数值太大。考虑n!中含有素因数p的个数，即确定素因数p对应的幂指数。我们知道n!包含了从1到n区间所有整数的乘积，这些乘积中每一个p的倍数（包括其本身）都对n!贡献至少一个p因子，且我们知道在1到n中p的倍数共有n/p个。同理，计算p^2，p^3,...即可
代码
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#defineN1001
intprime[N],size;
/**
*素数筛选法进行预处理
*/
voidinitProcess()
{
inti,j;
for(prime[0]=prime[1]=0,i=2;i<N;i++){
prime[i]=1;
}
size=0;
for(i=2;i<N;i++){
if(prime[i]){
size++;
for(j=2*i;j<N;j+=i){
prime[j]=0;
}
}
}
}
intmain(void)
{
inti,n,a,k,num,count,base,tmp,*ansbase,*ansnum;
//预处理
initProcess();
while(scanf("%d%d",&n,&a)!=EOF){
ansbase=(int*)calloc(size,sizeof(int));
ansnum=(int*)calloc(size,sizeof(int));
//将a分解质因数
for(i=2,num=0;i<N&&a!=1;i++){
if(prime[i]&&a%i==0){
ansbase[num]=i;
ansnum[num]=0;
while(a!=1&&a%i==0){
ansnum[num]+=1;
a=a/i;
}
num++;
}
}
//求最小的k
for(i=0,k=0x7fffffff;i<num;i++){
base=ansbase[i];
count=0;
while(base<=n){
count+=n/base;
base*=ansbase[i];
}
tmp=count/ansnum[i];
if(tmp<k)k=tmp;
}
printf("%d\n",k);
}
return0;
}
/**************************************************************
Problem:1104
User:wangzhengyi
Language:C
Result:Accepted
Time:0ms
Memory:916kb
****************************************************************/
约数个数定理
对于一个大于1的正整数n可以分解质因数：
n=p1^a1*p2^a2*p3^a3*...*pn^an
,则n的正约数的个数为：
(a1+1)*(a2+1)*...*(an+1)
.其中p1,p2,..pn都是n的质因数，a1,a2...an是p1,p2,..pn的指数
证明
n可以分解质因数：n=p1^a1*p2^a2*p3^a3*…*pk^ak,
由约数定义可知p1^a1的约数有:p1^0,p1^1,p1^2......p1^a1，共（a1+1）个;同理p2^a2的约数有（a2+1）个......pk^ak的约数有（ak+1）个
故根据乘法原理：n的约数的个数就是
(a1+1）*（a2+1）*（a3+1）*…*(ak+1)
题目3
题目描述：
输入n个整数,依次输出每个数的约数的个数
输入：
输入的第一行为N，即数组的个数(N<=1000)
接下来的1行包括N个整数，其中每个数的范围为(1<=Num<=1000000000)
当N=0时输入结束。
输出：
可能有多组输入数据，对于每组输入数据，
输出N行，其中每一行对应上面的一个数的约数的个数。
样例输入：
5
134612
样例输出：
1
2
3
4
6
代码
#include<stdio.h>
#include<stdlib.h>
#defineN40000
typedeflonglongintlint;
intprime[N],size;
voidinit()
{
inti,j;
for(prime[0]=prime[1]=0,i=2;i<N;i++){
prime[i]=1;
}
size=0;
for(i=2;i<N;i++){
if(prime[i]){
size++;
for(j=2*i;j<N;j+=i)
prime[j]=0;
}
}
}
lintnumPrime(intn)
{
inti,num,*ansnum,*ansprime;
lintcount;
ansnum=(int*)malloc(sizeof(int)*(size+1));
ansprime=(int*)malloc(sizeof(int)*(size+1));
for(i=2,num=0;i<N&&n!=1;i++){
if(prime[i]&&n%i==0){
ansprime[num]=i;
ansnum[num]=0;
while(n!=1&&n%i==0){
ansnum[num]+=1;
n/=i;
}
num++;
}
}
if(n!=1){
ansprime[num]=n;
ansnum[num]=1;
num++;
}
for(i=0,count=1;i<num;i++){
count*=(ansnum[i]+1);
}
free(ansnum);
free(ansprime);
returncount;
}
intmain(void)
{
inti,n,*arr;
lintcount;
init();
while(scanf("%d",&n)!=EOF&&n!=0){
arr=(int*)malloc(sizeof(int)*n);
for(i=0;i<n;i++){
scanf("%d",arr+i);
}
for(i=0;i<n;i++){
count=numPrime(arr[i]);
printf("%lld\n",count);
}
free(arr);
}
return0;
}
/**************************************************************
Problem:1087
User:wangzhengyi
Language:C
Result:Accepted
Time:190ms
Memory:1068kb
****************************************************************/