因子个数(PAT)

1.题目描述

一个正整数可以分解成一个或多个数组的积。例如36=223*3，即包含2和3两个因子。NowCoder最近在研究因子个数的分布规律，现在给出一系列正整数，他希望你开发一个程序输出每个正整数的因子个数。

2.输入描述:

输入包括多组数据。
每组数据仅有一个整数n (2≤n≤100000)。

3.输出描述:

对应每个整数，输出其因子个数，每个结果占一行。

4.输入例子:

30
26
20

5.输出例子:

3
2
2

6.解题思路：

首先循环求能整除n的数，然后对n整除，直到该数不能整除为止，计数+1，例如：20，能被2整除为10、5，但2只能算一个因子，不能算两个。
<mark>*在源代码中我们需要注意的是，如果i循环到sqrt（n），i是循环不到n的，例如26被2整除后的13，i是循环不到【根号26】（【根号26】≈5.）所以最后我们要加一个判断n是否等于1，那么为什么这样做？</mark>
当n特别大的时候，如果以i<=n作为循环条件，那么循环就会多判断（n-【根号n】）次，例如（10000-【根号10000】）次判断和仅仅需要判断一次（n！=1）相比较，时间复杂度差距是非常大的。

7.源代码：

#include<stdio.h>
#include<math.h>
int main()
{
	int i,n,count;
	while(scanf("%d",&n)!=-1)
	{
		count=0;
		for(i=2;i<=sqrt(n);i++)
		{	
			if(n%i==0)
			{
				while(n%i==0)
					n=n/i;	
				count++;
			}
		}
		if(n!=1)//*
			count++;
		printf("%d\n",count);
	}
	return 0;
}