Ý tưởng

Các ước chung của ~x~ và ~y~ là các ước của ~g=\gcd(x,y)~. Điều kiện thỏa mãn khi ~g=1~ hoặc ~g~ là số nguyên tố. Duyệt ~y~ từ ~1~ đến ~n~, bỏ qua ~y=x~, kiểm tra điều kiện trên.

Độ phức tạp

~O(n\sqrt n)~.