Giả thuyết Goldbach
Xem PDF
Điểm:
200 (p)
Thời gian:
1.0s
Bộ nhớ:
1G
Input:
bàn phím
Output:
màn hình
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 \(n\), bạn hãy đếm số lượng cặp số nguyên tố \(a , b (a ≤ b)\) mà \(a + b = n\).
Input
- Gồm một dòng chứa một số tự nhiên chẵn \(n\).
Output
- Gồm dòng chứa một số là số lượng cặp số nguyên tố \(a , b\) mà \(a ≤ b\) và \(a + b = n\)
Scoring
- Subtask \(1\) (\(50\%\) số điểm): \(n ≤ 10^3\).
- Subtask \(2\) (\(50\%\) số điểm): \(n ≤ 10^6\).
Example
Test 1
Input
10 Output
2
Bình luận
sàng bth ac đc ko admin
-
2
nguyendanghau2006
11:03 p.m. 11 Tháng 12, 2021
-
0
VoBaThongL921
11:43 a.m. 31 Tháng 10, 2021
-
0
minhtuanitk20
11:49 a.m. 31 Tháng 10, 2021
-
0
VoBaThongL921
11:24 a.m. 31 Tháng 10, 2021
-
0
minhtuanitk20
11:26 a.m. 31 Tháng 10, 2021
-
0
VoBaThongL921
11:34 a.m. 31 Tháng 10, 2021
-
0
minhtuanitk20
11:35 a.m. 31 Tháng 10, 2021
-
2
minhtuanitk20
11:25 a.m. 31 Tháng 10, 2021
2 bình luận nữađược nghe at, 1 đấm hehe
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\)
còn nếu sàng tuyến tính thì sao
được nhé bạn, mặc dù mình không phải \(admin\) 🙂
mình sàng bth + map nó sẽ chứ ko nhất thiết phải sàng tuyến tính
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à ;-;
cái check snt độ phức tạp O(sqrt(n)/6))
ok bạn