Một số nguyên dương X bất kì đều phân tích ra được thành: X = p_1^{k_1} \times p_2^{k_2} \times p_m^{k_m} trong đó p_1 \lt p_2 \lt ... \lt p_m và p_i là một số nguyên tố, k_i là một số nguyên dương với mọi i.
Khi đó thì tập các số nguyên tố sẽ là (p_1, p_2, ..., p_m). Như vậy nó sẽ chung tập các ước nguyên tố với số nguyên dương Y = p_1 \times p_2 ... p_m.
Từ đây cho chúng ta ý tưởng đưa mọi số nguyên dương về tích của các ước nguyên tố phân biệt của nó. Như vậy ban đầu chúng ta có các số nguyên dương từ L đến R, sau đó thì ta thay tất cả các số nguyên dương X thành tích tất cả các số nguyên tố khác nhau là ước của nó, gọi số đó là f(X). Lúc này bài toán trở thành đếm số cặp (A, B) mà f(A) = f(B).
Trước hết, việc đưa mỗi số nguyên dương X về f(X) với mọi X thuộc đoạn [L, R] thì chúng ta dùng sàng nguyên tố lưu pr[X] là số nguyên tố nhỏ nhất là ước của X, sau đó thì phân tích mỗi số nguyên dương (không lớn hơn 10^6) về f(X) với độ phức tạp O(log_X).
Khi đưa mỗi số nguyên dương X về f(X) xong thì chúng ta dùng phép đếm phân phối, gọi cnt(K) là số lượng giá trị X có f(X) = K trên đoạn [L, R], lúc đó thì số lượng cặp số bằng nhau và bằng K chính là \frac{cnt(K)∗(cnt(K)−1)}{2}. Từ đây có thể dễ dàng đưa ra kết quả bài toán với độ phức tạp O((R − L) \times log(10^6) )).