欢迎来到天天文库
浏览记录
ID:59311836
大小:14.00 KB
页数:2页
时间:2020-09-05
《阶乘的因数的个数.doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、给定两个数m,n求m!分解质因数后因子n的个数。这道题涉及到了大数问题,如果相乘直接求的话会超出数据类型的范围。下面给出一种效率比较高的算法,我们一步一步来。m!=1*2*3*……*(m-2)*(m-1)*m可以表示成所有和n倍数有关的乘积再乘以其他和n没有关系的 =(n*2n*3n*......*kn)*ohter other是不含n因子的数的乘积 因为kn<=m 而k肯定是最大值 所以k=m/n =n^k*(1*2*......*k)*other =n^k*k!*other 从这个表达式中可以提取出
2、k个n,然后按照相同的方法循环下去可以求出k!中因子n的个数。每次求出n的个数的和就是m!中因子n的总个数先说一个定理: 若正整数n可分解为p1^a1*p1^a2*...*pk^ak 其中pi为两两不同的素数,ai为对应指数 n的约数个数为(1+a1)*(1+a2)*....*(1+ak) 如180=2*2*3*3*5=2^2*3^2*5 180的约数个数为(1+2)*(1+2)*(1+1)=18个。 若求A/B的约数个数,A可分解为p1^a1*p2^a2*...*pk^
3、ak,B可分解为q1^b1*q1^b2*...*qk^bk,则A/B的约数个数 为(a1-b1+1)*(a2-b2+1)*(a3-b3+1)...*(ak-bk+1).然后说N的阶乘:例如:20!1.先求出20以内的素数,(2,3,5,7,11,13,17,19)2.再求各个素数的阶数e(2)=[20/2]+[20/4]+[20/8]+[20/16]=18;e(3)=[20/3]+[20/9]=8;e(5)=[20/5]=4;...e(19)=[20/19]=1;所以20!=2^18*3^8*5^4*...*19^1解释:
4、2、4、6、8、10、12、14、16、18、20能被2整除4、8、12、16、20能被4整除(即被2除一次后还能被2整除)8、16能被8整除(即被2除两次后还能被2整除)16能被16整除(即被2除三次后还能被2整除)这样就得到了2的阶。其它可以依次递推。所以在求N的阶乘质数因数个数时,从最小的质数开始,思路:给定两个数m,n求m!分解质因数后因子n的个数。这道题涉及到了大数问题,如果相乘直接求的话会超出数据类型的范围。下面给出一种效率比较高的算法,我们一步一步来。m!=1*2*3*……*(m-2)*(m-1)*m可以表示成所有和n倍数
5、有关的乘积再乘以其他和n没有关系的 =(n*2n*3n*......*kn)*ohter other是不含n因子的数的乘积 因为kn<=m 而k肯定是最大值 所以k=m/n =n^k*(1*2*......*k)*other =n^k*k!*other 从这个表达式中可以提取出k个n,然后按照相同的方法循环下去可以求出k!中因子n的个数。每次求出n的个数的和就是m!中因子n的总个数。
此文档下载收益归作者所有