NGTO - Phân tích thành tổng hai số nguyên tố

View as PDF
Submit solution
Points: 1.00 (partial)
Time limit: 0.5s
Memory limit: 256M
Author:
Hieu Nguyen
Problem type
Allowed languages
C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Cho một số nguyên dương ~n~. Bạn hãy đếm số cách phân tích số ~n~ thành tổng hai số nguyên tố khác nhau ~u,v\ (u< v)~.

Input

  • Số nguyên dương ~n\ (2≤n≤3×10^5)~.

Output

  • Dòng đầu ghi một số nguyên ~k~ là số cách phân tích thỏa mãn điều kiện đề bài. Nếu không có cách phân tích ghi số ~0~.
  • Trường hợp ~k>0, k~ dòng tiếp theo, dòng thứ ~i~ ghi hai số ~u_i,v_i\ (u_i< v_i)~ là cách phân tích thứ ~i~ theo yêu cầu: ~u_1< u_2<…< u_k~.

Sample

Input #1
82
Output #1
4
3 79
11 71
23 59
29 53
Input #2
11
Output #2
0

Hint

  • Số ~82~ có ~4~ cách phân tích ~82=3+79=11+71=23+59=29+53~. Cách phân tích ~82=41+41~ không được tính vì ~u=v~.
  • Số ~11~ không phân tích được.

Problem source: Chuyên Sơn La Online Judge

Comments

Please read the guidelines before commenting.


  • -1
    ntm_mtn  commented on Oct. 25, 2023, 4:32 p.m.

    ad ơi cho e xin editorial bài này đc ko ạ


    • 0
      Docladongnai  commented on Aug. 1, 2024, 2:33 p.m.

      sử dụng công thức vét cạn cx được bạn ạ