质数与合数
摘自维基百科：
质数，又称素数，指在大于1的自然数中，除了1和此整数自身外，无法被其他自然数整除的数（也可定义为只有1和本身两个因数的数）。
比1大但不是素数的数称为合数。1和0既非素数也非合数。素数在数论中有着非常重要的地位。
质因数分解 即 分解质因数 。每个合数都可以写成几个质数相乘的形式。其中每个质数都是这个合数的因数，叫做这个合数的分解质因数。 分解质因数只针对合数。分解质因数的算式的叫短除法。
更多知识请点击维基链接：http://zh.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0
更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/
在阶乘中的应用
问题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能奉献多少个k
nCount += N;
}
return nCount;
}
复杂度：O(logkN)。
问题2
求N!的二进制表示中最低位1的位置。
思路：二进制表示中最低位1的位置等价于二进制表示中末尾0的个数+1，进而等价于N！中质因子2的个数+1
FindZeroNum(N，2)+1;
作者：csdn博客 Duplan
以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索int
， 因子分解
， 素数
， 质数
， c++ 求素数问题
， 5项因数
， 求素数
， 个数
， 求50以内的素数
， 被3整除的数
， 被7整除的数
， 质因数
， 求n以内的素数
合数
质数和合数、什么是质数和合数、质数和合数教学设计、0是质数还是合数、质数合数，以便于您获取更多的相关知识。