Finding how many factors?

[Mats]

What is the most efficient algorithm for finding how many factors a number has? I've just been doing brute force division up to (n - 1) / 2 thus far. How can this be optimized?

[mik2718]

You can start by going up to sqrt(n) instead.

As soon as you have a factor, divide by this factor and start again using just the dividend.

Avoid trying products containing numbers you have already tried.
(example, if you have tried 2, don't try any more even numbers)

[Duthomhas]

...that depends on whether you are looking for all factors or just prime factors.

24 has factors:
1 24
2 12
3 8
4 6

If you stop looking for even values at 2 you'll miss 4 and 6.

[Mats]

I'm looking for all factors.

[ats15]

Get a list of prime numbers, see for example http://primes.utm.edu/lists/small/
Then go up the list, see if any of them is a factor. If it is, divide your number n, by that prime, and repeat the process with the new value. You store all the prime values. For example, 336, you need all primes up to sqrt(336)=18.3... The list is 2 3 5 7 11 13 17

2 is a factor the result of division is 168. For 168, 2 is a factor, then what is left is 84. For 84 2 is a factor, next is 42. For 42 2 is a factor next is 21. For 21 3 is a factor, next is 7. For 7 only 7 is a factor. So your number is 2^4*3*7. To find all factors, get all unique combinations of the 6 primes in this case: (one element) 2,3,7,(two elements)4,6,14,21(three elements) 8,12,28,42,( four elements)16,24,56,84, (five elements)48,112,168,(six elements)336. You may add 1 to this list

[cire]

Mats wrote:

What is the most efficient algorithm for finding how many factors a number has?

Mats wrote:

I'm looking for all factors.

If you're just looking to find out how many factors a number has, you don't need to actually calculate them.

See: http://www.wikihow.com/Find-How-Many-Factors-Are-in-a-Number