# Finding common factors for large numbers...

This topic is 3932 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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

##### Share on other sites
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.

##### Share on other sites
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

In the example, gcd(600,70) = 10 = 2^1 * 5^1, so the answer is (1+1)*(1+1) = 4.

##### Share on other sites
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.

##### Share on other sites
Quote:
 Original post by alvaroLet 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 isp_1^e_1 * p_2^e_2 * ... * p_n^e_nthen 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.

1. 1
2. 2
Rutin
19
3. 3
JoeJ
16
4. 4
5. 5

• 36
• 23
• 13
• 13
• 17
• ### Forum Statistics

• Total Topics
631703
• Total Posts
3001814
×