Finding common factors for large numbers...
Author
Hello, Community!
How can I find how many numbers divide two different numbers? It is not necessary to know what the numbers are, just how many.
Thanks,
Chad
I suppose you could just calculate the prime factorization the GCD of the two numbers, which you can obtain with the Euclidean algorithm. Then use the prime factorization to calculate the number of total factors.
Let me see if I understand. If your numbers are 600 and 70, you want your answer to be 4 (1, 2, 5 and 10)?
If that is the case, compute the gcd of the two numbers and find a factorization of the resulting number into primes. If that factorization is
p_1^e_1 * p_2^e_2 * ... * p_n^e_n
then your answer is (e_1+1)*(e_2+1)*...*(e_n+1).
In the example, gcd(600,70) = 10 = 2^1 * 5^1, so the answer is (1+1)*(1+1) = 4.
If that is the case, compute the gcd of the two numbers and find a factorization of the resulting number into primes. If that factorization is
p_1^e_1 * p_2^e_2 * ... * p_n^e_n
then your answer is (e_1+1)*(e_2+1)*...*(e_n+1).
In the example, gcd(600,70) = 10 = 2^1 * 5^1, so the answer is (1+1)*(1+1) = 4.
I am thinking Chad, that if you are doing the one, you may as well be doing the other. How big are these numbers?
You may as well create a list of factors for both numbers - say ListA and ListB using some integer factorisation algorithm. Filter ListA from ListB and the length of the filtered list is your answer.
You may as well create a list of factors for both numbers - say ListA and ListB using some integer factorisation algorithm. Filter ListA from ListB and the length of the filtered list is your answer.
Author
Quote:Original post by alvaro
Let me see if I understand. If your numbers are 600 and 70, you want your answer to be 4 (1, 2, 5 and 10)?
If that is the case, compute the gcd of the two numbers and find a factorization of the resulting number into primes. If that factorization is
p_1^e_1 * p_2^e_2 * ... * p_n^e_n
then your answer is (e_1+1)*(e_2+1)*...*(e_n+1).
In the example, gcd(600,70) = 10 = 2^1 * 5^1, so the answer is (1+1)*(1+1) = 4.
Thanks, exactly what I was looking for. The numbers were 10^40 and 20^30.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement