Hướng dẫn giải của F12: Hàm 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
Hàm f(x) là tổng các số nguyên tố nhỏ hơn hoặc bằng x (n <= 10^5). Kiểm tra f(n) có phải số nguyên tố không, in Yes hoặc No.
Sub 1: Thử chia từng số — ~O(n sqrt(n))~
Với mỗi i từ 2 đến n, kiểm tra nguyên tố bằng cách thử chia đến sqrt(i), cộng các số nguyên tố vào S. Sau đó kiểm tra S nguyên tố bằng cách thử chia đến sqrt(S).
Kết quả chấm: đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
// Kiem tra so nguyen to bang cach thu chia (vet can)
bool laNguyenTo(long long x) {
if (x < 2) return false;
for (long long i = 2; i * i <= x; i++)
if (x % i == 0) return false;
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n;
cin >> n;
long long s = 0;
for (long long i = 2; i <= n; i++)
if (laNguyenTo(i)) s += i; // f(n) = tong cac so nguyen to <= n
cout << (laNguyenTo(s) ? "Yes" : "No") << endl;
return 0;
}
Sub 2: Sàng Eratosthenes — ~O(n log log n)~
Dùng sàng để đánh dấu các hợp số trong [0; n], cộng các số nguyên tố trong sàng để có S. S khoảng 4*10^8 nên dùng long long và kiểm tra S bằng thử chia đến sqrt(S).
Kết quả chấm: đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
// Sang Eratosthenes tim tat ca so nguyen to <= n
vector<bool> isP(n + 1, true);
isP[0] = false;
if (n >= 1) isP[1] = false;
for (long long i = 2; i * i <= n; i++)
if (isP[i])
for (long long j = i * i; j <= n; j += i)
isP[j] = false;
long long s = 0;
for (int i = 2; i <= n; i++)
if (isP[i]) s += i;
// Kiem tra s co phai so nguyen to (s khoang 4e8 nen thu chia den sqrt(s) la du)
bool ok = (s >= 2);
for (long long i = 2; i * i <= s; i++)
if (s % i == 0) { ok = false; break; }
cout << (ok ? "Yes" : "No") << endl;
return 0;
}
Bình luận