You are viewing a single comment's thread. Return to all comments →

An efficient way to find all the factors for a number is to first find factors less than or equal to the root of the number.

For example for 26 the root is 5.099. Using the above method we have to test just 5 numbers instead of 25. Only 100 tests in case of 10000.

The factors greater than the root can be found by dividing the number by the factors less than or equal to the number.

Finding the intersection of the factors of all numbers is trivial after that.

With Scala:

val set = (1 to sqrt(n).ceil.toInt).filter(n % _ == 0).toSet set ++ set.map(n / _)

## Common Divisors

You are viewing a single comment's thread. Return to all comments →

An efficient way to find all the factors for a number is to first find factors less than or equal to the root of the number.

For example for 26 the root is 5.099. Using the above method we have to test just 5 numbers instead of 25. Only 100 tests in case of 10000.

The factors greater than the root can be found by dividing the number by the factors less than or equal to the number.

Finding the intersection of the factors of all numbers is trivial after that.

With Scala: