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