# Finding total number of divisors which divide 2 given numbers [duplicate]

Possible Duplicate:
Number of common divisors between two given numbers

I need to find the total number of divisors which divide both the numbers lets say N and M. Actually I tried to think about it a lot and searched at a lot of places for a possible answer. All I could think of was finding the prime factors and generating the actual divisors from the factors ? However this would take a lot of computation,therefore I need a much faster method performing much fewer operations? Is there any well known algorithm or formula for this problem or any derivable formula? I think the answer should be the number of divisors of the gcd of the 2 numbers.

-

## marked as duplicate by Gerry Myerson, William, LVK, Chris Eagle, t.b.Sep 11 '12 at 16:16

It is the number of divisors of the greatest common divisor (GCD) of N and M. You can find the GCD by the Euclidean algorithm, which does not require factoring. This is generally a smaller number than N or M, but then you need to factor it. You don't need to generate all the divisors, you can use the divisor function as the product of one more than the power of each prime dividing the GCD.

-
Do you mean "...the product of one more than the power of each prime..."? – Code-Guru Sep 4 '12 at 22:43
@Code-Guru: Yes, fixed – Ross Millikan Sep 4 '12 at 23:01

let x = gcd(n,m) (greatest common devisor) and then x - oiler(x) how to find the gcd u can read here - http://en.wikipedia.org/wiki/Greatest_common_divisor

how to calculate oiler function u can find here http://en.wikipedia.org/wiki/Euler%27s_totient_function

(oiler fuction give you all the number strangers to your number)

-
This doesn't answer the question. And learn how to spell the man's name: it's Euler. – Gerry Myerson Sep 4 '12 at 22:43