Hướng dẫn giải của F04: Tổng nguyên tố
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Cho số tự nhiên N, cần tính tổng tất cả các số nguyên tố nhỏ hơn hoặc bằng N.
Cách làm
Viết hàm kiểm tra một số có phải số nguyên tố hay không: số nhỏ hơn 2 không phải số nguyên tố, còn lại thử chia cho các số i từ 2 đến căn bậc hai của số đó. Sau đó duyệt các số từ 2 đến N, nếu là số nguyên tố thì cộng vào tổng. Với N không quá 1000 cách này đủ nhanh.
#include <bits/stdc++.h>
using namespace std;
// Kiểm tra x có phải số nguyên tố hay không
bool la_nguyen_to(int x) {
if (x < 2) {
return false;
}
// Chỉ cần thử các ước i từ 2 đến căn bậc hai của x
for (int i = 2; i * i <= x; i++) {
if (x % i == 0) {
return false;
}
}
return true;
}
int main() {
int n;
cin >> n;
long long tong = 0;
// Duyệt các số từ 2 đến n, cộng dồn các số nguyên tố
for (int i = 2; i <= n; i++) {
if (la_nguyen_to(i)) {
tong += i;
}
}
cout << tong << "\n";
return 0;
}
Bình luận