Sign in to follow this  
Chad Seibert

Finding common factors for large numbers...

Recommended Posts

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 this post


Link to post
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
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.

Share this post


Link to post
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 this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this