Nhà toán học Goldbach đưa ra giả thuyết như sau: “Mỗi số nguyên lớn hơn 3 có thể biểu diễn thành tổng của hai số nguyên tố”. Từ giả thuyết này, ta có phát biểu mới: “Mỗi số nguyên lớn hơn 11 đều có thể biểu diễn thành tổng của hai hợp số”. Ví dụ, số 15 = 6 + 9, 6 và 9 là hợp số. Yêu cầu: Bạn hãy viết chương trình đếm số cách phân tích số n thành tổng hai số nguyên a và b (1<a≤b và a, b là hợp số)? Chú ý: Một số tự nhiên m được gọi là hợp số nếu có nhiều hơn hai ước. Dữ liệu vào cho trong tệp văn bản PT.INP gồm một số nguyên n (12 ≤ n ≤ 10^6). Kết quả đưa ra tệp văn bản PT.OUT một số duy nhất là số cách phân tích tìm được. (Lập trình C++)
2 câu trả lời
#include <iostream>
#define maxn 1000005
using namespace std;
bool np[maxn];
int n, cnt;
/// sàng nguyên tố
void sieve(int lim) {
for (int i = 2; i * i <= lim; i++) {
if (!np[i]) {
for (int j = i * i; j <= lim; j += i)
np[j] = 1;
}
}
}
int main() {
cin >> n;
sieve(n);
for (int i = 4; (i << 1) <= n; i++) {
if (np[i]) {
cnt += np[n - i];
}
}
cout << cnt;
}
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX = 1e6;
bool prime[MAX + 1];
ll n, cnt = 0;
void sieve() {
memset(prime, true, sizeof(prime));
prime[0] = prime[1] = false;
for(int i = 2; i * i <= n; ++i) {
if(prime[i]) {
for(int j = i * i; j <= n; j += i)
prime[j] = false;
}
}
}
int main() {
cin >> n;
sieve();
for(int i = 4; i <= n - 4; ++i)
if(!prime[i] && i <= n - i)
cnt += !prime[n - i];
cout << cnt;
}
Câu hỏi trong lớp
Xem thêm
- Đề thi học kì 2 môn địa 8 có lời giải chi tiết
- Đề thi học kì 2 môn địa 8 có lời giải chi tiết
- Đề thi học kì 2 môn địa 8 có lời giải chi tiết giúp các em luyện tập và củng cố kiến thức hiệu quả
- Kiểm tra 15 phút lần 1 học kì 1 - đề số 5 Địa 8 có lời giải chi tiết
- Kiểm tra 15 phút lần 1 học kì 1 - đề số 4 Địa 8 có lời giải chi tiết
