Ý tưởng

Nếu ~d~ là ước nhỏ nhất của ~n~ lớn hơn ~1~, thì ~n/d~ là ước thực sự lớn nhất. Duyệt ~d~ từ ~2~ đến ~\sqrt n~; nếu không tìm được ước nào thì ~n~ là số nguyên tố và đáp án là ~1~.

Độ phức tạp

~O(\sqrt n)~.