Bài 3. Đếm cặp nguyên tố (PAIRPRIME)

🔗 Problem: [HSG_Số Học]. Bài 3. Đếm cặp nguyên tố (PAIRPRIME)

Ý tưởng

Trường hợp 1: $x$ hoặc $y$ là số nguyên tố $\quad \Rightarrow \quad$ Số cách chọn: $\text{prime_count} * (n - \text{prime_count})$

Trường hợp 2: $x$ và $y$ là số nguyên tố $\quad \Rightarrow \quad$ Số cách chọn: $\binom{n}{2} = \frac{\text{prime_count} * (\text{prime_count} + 1)}{2}$

$\quad \Rightarrow \quad$ Vậy số cách chọn là: $\text{prime_count} * (n - \text{prime_count})$ + $\frac{\text{prime_count} * (\text{prime_count} + 1)}{2}$

Mã giải (C++)

main.cpp