2. 约数的个数

题目描述

输入n个整数,依次输出每个数的约数的个数

输入描述:

输入的第一行为N，即数组的个数(N<=1000)
接下来的1行包括N个整数，其中每个数的范围为(1<=Num<=1000000000)
当N=0时输入结束。

输出描述:

可能有多组输入数据，对于每组输入数据，
输出N行，其中每一行对应上面的一个数的约数的个数。

示例1

输入

5
1 3 4 6 12

输出

1
2
3
4
6

---

解法

#include<stdio.h>

int main(){
    int j,num,temp,count;    //num为输入的数的个数，count为约数个数
    while(scanf("%d", &num)!=EOF){    //牛客网C语言只能这样控制多组输入
    for(int i = 0; i < num; i++){
        scanf("%d", &temp);
        count = 1;
        for(j = 2; j * j < temp; j++){
            if(temp % j == 0)
                count += 2;
        }
        if(j * j == temp)
            count++;
        if(temp > 1)
            count++;
        printf("%d\n", count);
    }
        
}
    return 0;
}

注意约数判断条件：
（1）1一定是约数，所以至少有1个；
（2）大于1的话自己本身也是；
（3）求a的约数，只用试到根号n，接下来证明这个原理：
假设a<√n，n%a=0，则a是n的一个约数，且n/a也是n的一个约数，所以每个小于√n的约数对应着两个n的约数，当a=√n时，a是唯一一个约数。