CODEWITHSUNDEEP
pythoncountergreatest-common-divisor
mcmoistener
mcmoistener

Reputation: 21

gcd from 2 factorisation lists using counters python

I need to get the greatest common divisor of 2 numbers using their factorizations the factorizations will be put in counters

c=Counter(factorslist(a))
d=Counter(factorslist(b))

So I want to add the lists together like

g=c and d

and then my multiplying whats inside the counter by each other i should be able to get the gcd so if g is (2,2,3,8) i want it to calculate 2*2*3*8.

I'm having a lot of trouble, is there already a counter function that does this? or do i need a loop to systematicaly times each number together? do i need to convert it to sets or something first?

UPDATE: alright so what ive done is added them together using g=c&d woks fine now im trying to get my algorithm working sol=1 for i in range(maxg+1): if g[i]!=0: k=g[i] sol=sol*(ik) return sol so im checking how many of each number are in the common factors list of g and multiplying the number by the number of them and then multiplying sol by that eg five two's is sol=sol(5*2). this seems to work with numbers with low gcds about 30 and less i think? and it works for coprimes, but if i run this with say 1000,500 i get 60 back... even tho 1000 and 990 gives me 10 back.

Upvotes: 2

Views: 168

Answers (1)

Prune
Prune

Reputation: 77850

First, I think you've misunderstood a couple of things: (1) The factorization is into primes -- 8 would be factored into 2*2*2 (2) Counter is not a list; it's a dictionary. The list [2, 2, 3, 7] would be the counter object {2:2, 3:1, 7:1}

Thus, what you need is the "min" function on the counts of the common factors. Then you need to multiply things in a resulting loop.

Can you take it from there? See what you can work through; post again with your progress if you get stuck.

Upvotes: 1

Related Questions