wtorek, 16 października 2018

Codility-CommonPrimeDivisors version by GCD

It's tricky task. I used some help via internet.
Idea:  Greatest common divisor of A and B consists of EVERY prime divisor of A & B. Consists or contains. There is no such a number E that would be prime, and divisor of A and B that GCD(A,B) * E = A && GCD(A,B) * E =B

Once you have GCD, you divide a number by it. That number can be considered as a "row" of prime factors and their exponents. So dividing number by GCD will remove some factors or their exponents.

Then you create a new GCD value form divided number and old GCD value. And repeat dividing. Eventually GCD will become = 1. Then there are two possibilities:
(last) divided number = 1 number consisted only with prime divisors contained in original GCD
(last) divided number != 1 number consists of some more prime divisors than original GCD

Brak komentarzy:

Prześlij komentarz