Wspólny dzielnik dwóch liczb.

Question

Cześć. Mój problem jest następujący:

Szukam najwydajniejszego sposobu na sprawdzenie czy dwie liczby(x i y) są pierwsze względem siebie. Doszedłem do wniosku, że nie mogą mieć wspólnego dzielnika oprócz 1.

Muszę je dzielić przez wszystkie liczby zaczynając od 2? czy może macie jakiś lepszy pomysł?

Comments

Dla Twoich potrzeb algorytm Euklidesa w wersji z dzieleniem modulo będzie wystarczający.

Answer 1

https://en.wikipedia.org/wiki/Binary_GCD_algorithm

Answer 2

Zobacz sobie algorytm Euklidesa. Nie wiem czy jest najwydajniejszy, ale działa