Ý tưởng

Dùng nguyên lý bao hàm-loại trừ. Với mỗi tập con không rỗng của các số nguyên tố, gọi tích các phần tử là ~P~. Số bội của ~P~ trong đoạn ~[1,n]~ là ~\lfloor n/P \rfloor~. Nếu kích thước tập con lẻ thì cộng, nếu chẵn thì trừ. Khi nhân tích cần bỏ qua nhánh có tích vượt quá ~n~ để tránh tràn số.

Độ phức tạp

~O(2^k)~.