质数的定义

除了 1 和自身，找不到其它因数的数。例如 7 和 13 都是质数。

最小的质数是 2 。

合数

除了 1 和自身，能找到其它因数的数。例如 10,16 均是合数。

最小和合数是 4 。

特殊情况

数字 1 既不是质数，也不是合数。这个特殊情况一定要牢记，在写程序的需要可能需要加一个特殊判断分支。

1. 判断一个数是不是质数。

因为质数不可能包含 1 和自身以外的别的因数，所以，一个个数去枚举测试，如果找不到 1 和 自身以外的因数，就可以判断这个数位质数。

但是，上面这个办法很笨，如果遇到很大的质数那么枚举的次数是非常多的。实际上可以进一步优化： 只需要枚举从 2 到 sqrt(n) 即可，如果找不到因数就可以判断 n 是质数 。

如果有 i 是 n 的因数，那么 n/i 也一定是 n 的因数。 i 和 n/i 两个数起码有一个数是小于等于 sqrt(n) 的。我们可以用反证法轻松的证明这一点。也就是说，如果一个数是合数，那么肯定找得到至少 1 个因数是小于等于它的平方根的，如果找不到，则可以推断出它就是质数。这一点小小的改进所带来的好处是巨大的。以 9999999979 为例，这是一个很大的质数，如果用笨方法，就要从 2 一直枚举到 9999999979 ，而优化之后，只需要从 2 枚举到 37550 ( sqrt(9999999979) 取整之后是 37550 ），9999999979 和 37550 相差了很多个数量级。

bool prime_check(int n)
{
	for(int i=2;i<=sqrt(n);i++)
		if(n%i==2)
			return false;
	
	return true;
}

2. 暴力枚举分解质因数

枚举 2 到 n 之间的数，只要是 n 的因数就分解，分解的时候用 while 语句，因为有可能同一个因数包含了多个，例如 48 就包含了 4 个质因数 2。

因为是从小到大枚举的，所以，分解出来的因数一定数是从小到大，一定就是质因数了。例如分解 48 ， 虽然 12 也是一个因数，但是因为枚举到 2 的时候就把所有的因数 2 分解掉了，枚举到 3 的时候又把所有的因数 3 分解掉了，因此不会分解出因数 12 。

	for(i=2;n>1;i++) //如果 n 变成 1 就不用分解了，这可以作为循环的退出条件 
	{
		while(n%i==0)
		{
			printf("%d ",i);
			n /= i;
		}			
	}

3. 对一个更大的数字分解质因数

当遇到一个很大的 n ，而且 n 是一个质数，那么上面的方法会一直从 2 枚举到 n，运算复杂度很大，很容易导致超时。还是可以利用质数判断的知识，我们只枚举到 sqrt(n)，如果还没有能够把 n 分解成 1，那么我们就认为 n 是一个质数。所以，离开循环之后，要补充做一次判断。

	int nn = sqrt(n); // sqrt函数返回的是浮点数，赋值给 int 变量 nn 的时候做了强制转换，小数部分被截断 
	for(i=2;i<=nn;i++)
	{
		while(n%i==0)
		{
			printf("%d ",i);
			n /= i;
		}
		if(n==1) break; //有这句是可以更快一些，没有也问题不大 
	}

	if(n!=1) //说明了 n 是质数。对一个质数分解质因数就是输出它自己 
		printf("%d",n);

4. 因数的个数

如果 i 是 n 的因数，说明了 i 能整除 n ，假设 n/i = j , 那意味着 j 也是 n 的因数。 所以， i 和 n/i 是 一对因数，知道一个就可以算出另外一个。

在某些情况下 i 和 n/i 是同一个数，例如当 n = 144 ， i = 12 的时候 n/i=144/12=12 。只有当 n 是平方数的时候才会有这个情况。

有一些题目会让学生计算 n 的因数个数，用笨方法，就是从 1 枚举到 n ；通过上面的数学知识，我们可以改进一下：

• 枚举 i ,从 1 枚举到 sqrt(n) , 如果 i 是 n 的因数，则答案增加 2
• 最后，如果 n 是完全平方数，则总数减一

	int cnt = 0;
	for(int i=2;i<=sqrt(n);i++)
		if(n%i==0)
			cnt += 2;

	int j = sqrt(n);
	if(j*j==n)
		cnt--;