Đếm Cặp Phần Tử Có Tổng Nguyên Tố

Buổi 60 — FFT / NTT Mathematics Number Theory
Points
45
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
number
Submissions
Đề bài

Cho một dãy gồm $N$ số nguyên dương $A_1, A_2, \dots, A_N$. Bạn hãy đếm số lượng cặp chỉ số $(i, j)$ thỏa mãn $1 \le i < j \le N$ sao cho tổng $A_i + A_j$ là một số nguyên tố.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $N$ ($2 \le N \le 5 \cdot 10^4$). Dòng thứ hai chứa $N$ số nguyên dương $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 50\,000$).

Dữ liệu ra

In ra một số nguyên duy nhất là số cặp $(i, j)$ có tổng là số nguyên tố.

Ví dụ
Input Output
4
1 2 3 4
4
Giới hạn

Thời gian: 1.0s, Bộ nhớ: 256MB.

Draft saved