质数与合数及其应用

质数与合数及其应用2014-12-25

质数与合数

摘自维基百科：

质数，又称素数，指在大于1的自然数中，除了1和此整数自身外，无法被其他自然数整除的数（也可定义为只有1和本身两个因数的数）。

比1大但不是素数的数称为合数。1和0既非素数也非合数。素数在数论中有着非常重要的地位。

质因数分解 即分解质因数。每个合数都可以写成几个质数相乘的形式。其中每个质数都是这个合数的因数，叫做这个合数的分解质因数。分解质因数只针对合数。分解质因数的算式的叫短除法。

更多知识请点击维基链接：http://zh.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0

在阶乘中的应用

问题1

求N！末尾0的个数

方法1.采用质因数分解法。

//统计 1-N 中被5整除的因子的总个数 int FindZeroNum（int N）{int nCount = 0;for （int i = 5;i < N + 1;i++）{int nCur = i;while（nCur % 5 == 0）//统计nCur中被5整除的因子的个数，即有几个5{nCount++;nCur /= 5;}}return nCount;}

方法2.

N！中含有的质因数k的个数为：[N/k]+[N/k^2]+[N/k^3]+...

其中，[N/k]表示不大于N的数中（1--N）k的倍数贡献一个k

[N/k^2]表示不大于N的数中k^2的倍数贡献一个k

......

int FindZeroNum（int N，int k）//求N！中含有多少个质因子k{int nCount = 0;while（N）{N = N / k; //1-N能奉献多少个knCount += N;}return nCount;}

复杂度：O（logkN）。

问题2

求N！的二进制表示中最低位1的位置。

思路：二进制表示中最低位1的位置等价于二进制表示中末尾0的个数+1，进而等价于N！中质因子2的个数+1

FindZeroNum（N，2）+1;

作者：csdn博客 Duplan