前言
之前就想写一篇关于分解质因数的文章，原因也是九度oj上有几道跟质因数分解有关的题目没有思路，这次找完工作学java的同时进行一些查缺补漏
原理&&方法
把一个合数分解为若干个质因数的乘积的形式，即求质因数的过程叫做分解质因数，分解质因数只针对合数
求一个数分解质因数，要从最小的质数除起，一直除到结果为质数为止。分解质因数的算式的叫短除法，和除法的性质差不多，还可以用来求多个个数的公因式：
以24为例：
2 -- 24
2 -- 12
2 -- 6
3 （3是质数，结束）
得出 24 = 2 × 2 × 2 × 3 = 2^3 * 3
代码
可先用素数筛选法，筛选出符合条件的质因数，然后for循环遍历即可，通过一道题目来show一下这部分代码
题目
[html]
题目描述：
求正整数N（N>1）的质因数的个数。
相同的质因数需要重复计算。如120=2*2*2*3*5,共有5个质因数。
输入：
可能有多组测试数据，每组测试数据的输入是一个正整数N,（1<N<10^9）。
输出：
对于每组数据，输出N的质因数的个数。
样例输入：
120
样例输出：
5
提示：
注意：1不是N的质因数；若N为质数，N是N的质因数。
ac代码
[cpp]
#include <stdio.h>
int main（）
{
int n, 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）；
}
return 0;
}
深入理解
我所谓的深入理解，就是通过4星的题目来灵活运用分解质因数的方法，题目如下
题目
[html]
题目描述：
给定n,a求最大的k,使n!可以被a^k整除但不能被a^（k+1）整除。
输入：
两个整数n（2<=n<=1000），a（2<=a<=1000）
输出：
一个整数。
样例输入：
6 10
样例输出：
1
思路
a^k和n!都可能非常大，甚至超过long long int的表示范围，所以也就不能直接用取余操作判断它们之间是否存在整除关系，因此我们需要换一种思路，从分解质因数入手，假设两个数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,…即可
代码
[cpp]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 1001
int prime[N], size;
/**
* 素数筛选法进行预处理
*/
void initProcess（）
{
int i, j;
for （prime[0] = prime = 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;
}
}
}
}
int main（void）
{
int i, 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）；
}
return 0;
}
/**************************************************************
Problem: 1104
User: wangzhengyi
Language: C
Result: Accepted
Time:0 ms
Memory:916 kb
****************************************************************/