深入分析C语言分解质因数的实现方法.docx

首先来看一个最简单的C语言实现质因数分解的列子：?123456789101112131415#include stdio.hvoidmain( ){??intdata, i = 2;??scanf(%d, data);??while(data 1)??{????if(data % i == 0)????{??????printf(%d , i);??????data /= i;????}????elsei++;??}}原理方法把一个合数分解为若干个质因数的乘积的形式，即求质因数的过程叫做分解质因数，分解质因数只针对合数求一个数分解质因数，要从最小的质数除起，一直除到结果为质数为止。分解质因数的算式的叫短除法，和除法的性质差不多，还可以用来求多个个数的公因式：以24为例：2 -- 242 -- 122 -- 63 （3是质数，结束）得出 24 = 2 × 2 × 2 × 3 = 2^3 * 3代码可先用素数筛选法，筛选出符合条件的质因数，然后for循环遍历即可，通过一道题目来show一下这部分代码题目1??? 题目描述：????? 求正整数N(N1)的质因数的个数。????? 相同的质因数需要重复计算。如120=2*2*2*3*5，共有5个质因数。????? 输入：????? 可能有多组测试数据，每组测试数据的输入是一个正整数N，(1N10^9)。????? 输出：????? 对于每组数据，输出N的质因数的个数。????? 样例输入：????? 120????? 样例输出：????? 5????? 提示：????? 注意：1不是N的质因数；若N为质数，N是N的质因数。?ac代码????123456789101112131415161718192021222324252627#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)????? 输出：????? 一个整数.????? 样例输入：????? 6 10????? 样例输出：????? 1?思路a^k和n!都可能非常大，甚至超过long longint的表示范围，所以也就不能直接用取余操作判断它们之间是否存在整除关系，因此我们需要换一种思路，从分解质因数入手，假设两个数a和b：?1a = p1^e1 * p2^e2 * ... * pn^en, b = p1^d1 * p2^d2 * ... * pn^dn, 则b除以a可以表示为：?1b / 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,...即可代码????123456789101112131415161718192021222324252627282