Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2 Answers 2

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.

share|improve this answer
    
Do you mean "...the product of one more tha*n* 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)

share|improve this answer
1  
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

Not the answer you're looking for? Browse other questions tagged or ask your own question.