Sign in to follow this  

Finding common factors for large numbers...

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

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

If you intended to correct an error in the post then please contact us.

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