Bài 4. Nửa nguyên tố (SEMIPRIME)

🔗 Problem: [HSG_Số Học]. Bài 4. Nửa nguyên tố (SEMIPRIME)

Ý tưởng

Ta có $n = x*y$ với x và y là số nguyên tố, giả sử $x \leq y$ thì:

\[x^2 \leq xy \leq n\]

Qua đó, ta suy ra:

\[\begin{align*} x &\leq \sqrt{n} \\[1mm] y &\ge x \end{align*}\]

Lồng for thì độ phức tạp tổng thể chỉ mất $O(n)$, hoàn toàn AC được

Mã giải (C++)

main.cpp