题目
题目描述:
输入n个整数,依次输出每个数的约数的个数
输入描述:
输入的第一行为N，即数组的个数(N<=1000)
接下来的1行包括N个整数，其中每个数的范围为(1<=Num<=1000000000)
当N=0时输入结束。
输出描述:
可能有多组输入数据，对于每组输入数据，
输出N行，其中每一行对应上面的一个数的约数的个数。
思路
这道题做的时候真的是走了死胡同，过不去的原因就是时间过长导致，这种题很容易想到的一种解法就是暴力算法：将所有小于X的数据全部都除一遍肯定能找全所有的约数，但是一个用例的测试让我清醒这根本不可能一共999个数据，每个数据9位，这样做肯定在1秒内的不出最终答案
那就换个方法google一下发现可以用约数个数定理，找出所有质因数的指数后加1乘起来，结果找质因数又成了一个大问题，有这个时间还不如跑最简单的那个思想呢，下面就开始google怎么才能找出一个大数据的所有质因子，结果出现了两种筛法埃拉托斯特尼筛法和欧拉筛法，但是欧拉筛法没看懂，埃拉托斯特尼筛法看懂了，思想比较简单就是如果找到一个数是质数，那么其倍数一定是合数，就全部剔掉，剩下的就是质数了，代码实现
private static int[] getPrime(int x){
int[] isPrimes = new int[x];
for (int i = 2; i < x; i++)
isPrimes[i] = i;
isPrimes[0] = 0;
isPrimes[1] = 0;
for(int i = 2;i < x; i++){
if(isPrimes[i] != 0){
for (int j = i + i;j < x; j += i){
isPrimes[j] = 0;
}
}
}
int j = 0;
int[] prams = new int[x];
for(int i = 0;i < x;i++){
if (isPrimes[i] != 0)
prams[j++] = isPrimes[i];
}
return prams;
}
}
结果还是太慢，数据太多处理不过来，也可能是我算法的问题。结果就换了最后一种人家已经想到的算法，思想是
1.如果这个数是1那就只能有一个约数了
2.如果这个数大于1那么肯定至少有两个质因数，而且一个在Math.sqrt(X)的左边，一个在Math.sqrt(X)右边，否则两个数要么乘起来大于X要么不够，这里排除其质因数俩相等的情况,因为两个相等会多加1个，这也是for(j = 1;j < Math.sqrt(data);j++)不加等号的原因。
3.处理最后的j * j == X的情况，因为有可能会漏掉这个，也是因为第二步可能会出现这种情况
我认为这里面最重要的就是
for(j = 1;j < Math.sqrt(data);j++){ //使用定理
if(data % j == 0)
sum += 2; //这里最精彩，直接标记两个因子成为约数
}
if(data == 1) // 这里是因为如果data是1的话是不能走下面的否则就会变成2了
sum = 1;
else{
int j;
for(j = 1;j < Math.sqrt(data);j++){ //使用定理
if(data % j == 0)
sum += 2; //这里最精彩，直接标记两个因子成为约数
}
if(j * j == data) //到这里j*j有两种可能一个是大于data另外一个是等于data，
sum++; //大于data的情况不用说，j已经超过了sqrt(data)
} //而等于data是容易漏掉的，因为在上面的循环中不加等号，也不能加
//等号，因为sum+=2,所以放在这里特殊处理
