Finding all the factors of a given number

九度-1087 约数的个数[数论]
2011年清华大学计算机研究生机试真题输入n个整数,依次输出每个数的约数的个数
X. 用约数个数定理  http://baike.baidu.com/view/1780622.htm 
Get prime factors

对于一个大于1正整数n可以分解质因数：

则n的正约数的个数就是

。

其中a₁、a₂、a₃…a_k是p₁、p₂、p_3，…p_k的指数。

不用进行素数判定，for循环找到的 i 一定是素数。
经验证，平均性能比穷举法（O(n)）的速度快很多，10^12左右的合数都能瞬间出结果，穷举法要好几秒(不过对于素数，该算法就退化为穷举法了，也就是说最坏情况下时间复杂度为O(n))。

01	unsigned int factors(unsigned int n)

02

{

03	unsigned int i = 2, k = 0, m = n, count = 1;

04	while(m != 1)

05

{

06	for(; i <= m; i ++)

07	if(m % i == 0)

08

{

09

k = 1;

10	while(m % i == 0)

11

{

12

k ++;

13

m /= i;

14

}

15	count *= k;

16

}

17

}

18	return count;

19

}

X. Brute Force

14	int count = 0;

15	cin >> num;

16

17

int i;

18	for (i = 1; i < sqrt((double)num); i++)

19

{

20	if (num % i == 0)

21

{

22	count += 2;

23

}

24

}

25	if (i * i == num)

26

{

27

count++;

28

}

29	cout << count << endl;

Problem solving with programming: Finding all the factors of a given number

Given a number, how do we write a program to find all of it's factors or divisors.

factorList.add(1);
for( i = 2; i <= sqrt(n); i++ )
{
    if( n % i == 0 )
    {
       factorList.add(i);
       if( i != sqrt(n) )
          factorList.add(n/i);
    }
}
factorList.add(n);

Read full article from Problem solving with programming: Finding all the factors of a given number