Giả thuyết Goldbach

View as PDF

Submit solution


Points: 200 (partial)
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout

Author:
Problem types

Giả thuyết Goldbach do nhà toán học người Đức Christian Goldbach (1690-1764) nêu ra vào năm 1742 trong một lá thư gửi tới Leonhard Euler, là một trong những bài toán lâu đời và nổi tiếng còn chưa giải được trong lý thuyết số nói riêng và toán học nói chung. Giả thuyết phỏng đoán rằng: Mọi số tự nhiên chẵn lớn hơn 2 có thể biểu diễn bằng tổng của hai số nguyên tố. Trong bài toán này bạn được cho một số tự nhiên chẵn ~𝑛~, bạn hãy đếm số lượng cặp số nguyên tố ~𝑎, 𝑏\ (𝑎 ≤ 𝑏)~ mà ~𝑎 + 𝑏 = 𝑛~.

Dữ liệu • Gồm một dòng chứa một số tự nhiên chẵn ~𝑛~.

Kết quả • Gồm dòng chứa một số là số lượng cặp số nguyên tố ~𝑎, 𝑏~ mà ~𝑎 ≤ 𝑏~ và ~𝑎 + 𝑏 =n~

Sample input

10

Sample output

2

Ràng buộc

  • Có 50% test ứng với 50% số điểm có ~𝑛 ≤ 10^3~;
  • Có 50% test còn lại ứng với 50% số điểm có ~𝑛 ≤ 10^6~

View comments (16)

Comments


  • 2
    minhtuanitk20  commented on 11:16 a.m. 31 oct, 2021

    sàng bth ac đc ko admin


    • -2
      nguyendanghau2006  commented on 11:03 p.m. 11 dec, 2021

      được nghe at, 1 đấm hehe


    • 1
      VoBaThongL921  commented on 11:43 a.m. 31 oct, 2021

      mình check số nguyên tố thông thường và duyệt ~6k+-1~ thì time ~1.56s~ còn sàng nguyên tố của mình mất ~0.18s~


      • 1
        minhtuanitk20  commented on 11:49 a.m. 31 oct, 2021

        còn nếu sàng tuyến tính thì sao


    • 0
      VoBaThongL921  commented on 11:24 a.m. 31 oct, 2021

      được nhé bạn, mặc dù mình không phải ~admin~ :)


      • 1
        minhtuanitk20  commented on 11:26 a.m. 31 oct, 2021

        mình sàng bth + map nó sẽ chứ ko nhất thiết phải sàng tuyến tính


        • 0
          VoBaThongL921  commented on 11:34 a.m. 31 oct, 2021

          ye mình dùng kiểm tra tình nguyên tố 6k+-1 cơ bản mà còn không bị tle mà ;-;


          • 0
            minhtuanitk20  commented on 11:35 a.m. 31 oct, 2021

            cái check snt độ phức tạp O(sqrt(n)/6))


      • 2
        minhtuanitk20  commented on 11:25 a.m. 31 oct, 2021

        ok bạn


  • -28
    N7hoatt  commented on 8:35 p.m. 12 jul, 2020

    This comment is hidden due to too much negative feedback. Click here to view it.


    • -2
      lagiahuy  commented on 8:33 p.m. 8 oct, 2021

      sao nhiều downvote thế


    • -20
      nguyenquochuy  commented on 4:08 p.m. 5 aug, 2020

      This comment is hidden due to too much negative feedback. Click here to view it.


      • -3
        lagiahuy  commented on 8:34 p.m. 8 oct, 2021

        mà sao nhiều downvote thế


      • -3
        lagiahuy  commented on 8:33 p.m. 8 oct, 2021

        đc chứ


      • -16
        khangts714  commented on 4:34 p.m. 6 aug, 2020

        This comment is hidden due to too much negative feedback. Click here to view it.


      • -27
        N7hoatt  commented on 4:14 p.m. 5 aug, 2020

        This comment is hidden due to too much negative feedback. Click here to view it.