Ý tưởng

Tổng lớn nhất là ~2\cdot 10^6~, nên có thể sàng nguyên tố trước. Sau đó duyệt các cặp và kiểm tra ~a_i+a_j~ trong ~O(1)~. Có thể tối ưu bằng đếm tần suất: ngoài cặp ~1+1=2~, mọi tổng nguyên tố còn lại là số lẻ, do đó chỉ cần ghép một số chẵn với một số lẻ.

Độ phức tạp

~O(2\cdot 10^6+n^2)~ với cách duyệt cặp, hoặc tốt hơn khi dùng tần suất.