Hướng dẫn giải của Số nguyên tố đối xứng
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.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Cho hai số m và n (1 ≤ m ≤ n ≤ 10^8). Yêu cầu tìm tất cả các số nguyên tố đối xứng nằm trong khoảng từ m đến n (bao gồm cả m và n). Số nguyên tố đối xứng là số vừa là số nguyên tố vừa là số đối xứng (ví dụ: 2, 11, 101). Nếu không có số nào, in ra 0.
Các cách tiếp cận
Cách Brute Force (Kiểm tra từng số)
#include <bits/stdc++.h>
using namespace std;
bool isPrime(int n) {
if (n < 2) return false;
for (int i = 2; i * i <= n; i++)
if (n % i == 0) return false;
return true;
}
bool isPalindrome(int n) {
string s = to_string(n);
string t = s;
reverse(t.begin(), t.end());
return s == t;
}
int main() {
int m, n;
cin >> m >> n;
bool found = false;
for (int i = m; i <= n; i++) {
if (isPrime(i) && isPalindrome(i)) {
cout << i << "\n";
found = true;
}
}
if (!found) cout << 0;
return 0;
}
- Time Complexity: O((n-m) * sqrt(n) + D * log n) ~ O(n * sqrt(n))
- Space Complexity: O(1)
Phương pháp này duyệt qua từng số trong khoảng [m, n]. Với mỗi số, nó kiểm tra hai điều kiện: (1) Có phải là số nguyên tố không bằng cách lặp từ 2 đến căn bậc hai của số đó. (2) Có phải là số đối xứng không bằng cách so sánh chuỗi số với chuỗi đảo ngược của nó. Đây là cách tiếp cận trực quan nhất nhưng chậm chạp khi khoảng cách n-m lớn.
Cách Sàng Eratosthenes (Pre-compute Primes)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e8;
vector<bool> isPrime(N + 1, true);
void sieve() {
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= N; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= N; j += i)
isPrime[j] = false;
}
}
}
bool isPalindrome(int n) {
string s = to_string(n);
int l = 0, r = s.length() - 1;
while (l < r) {
if (s[l] != s[r]) return false;
l++; r--;
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
sieve();
int m, n;
cin >> m >> n;
bool found = false;
for (int i = m; i <= n; i++) {
if (isPrime[i] && isPalindrome(i)) {
cout << i << "\n";
found = true;
}
}
if (!found) cout << 0;
return 0;
}
- Time Complexity: O(N log log N + (n-m) * log n)
- Space Complexity: O(N) ~ 100MB
Sử dụng sàng Eratosthenes để pre-compute trạng thái nguyên tố cho tất cả các số từ 1 đến 10^8. Việc kiểm tra nguyên tố sau đó trở thành tra cứu mảng O(1). Cách này tăng tốc độ kiểm tra nguyên tố đáng kể so với việc tính toán lại mỗi lần, nhưng tốn bộ nhớ để lưu mảng (khoảng 100MB).
Cách Tạo số đối xứng (Digit Generation)
#include <bits/stdc++.h>
using namespace std;
bool isPrime(long long n) {
if (n < 2) return false;
if (n == 2 || n == 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
for (long long i = 5; i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) return false;
}
return true;
}
void solve() {
long long m, n;
cin >> m >> n;
bool found = false;
// 1. Chữ số lẻ (1, 3, 5, 7, 9)
for (long long i = 1; i <= 9; i += 2) {
if (i >= m && i <= n && isPrime(i)) {
cout << i << "\n";
found = true;
}
}
// 2. Các số đối xứng có 2 chữ số (11, 33, 55, 77, 99)
for (long long i = 1; i <= 9; i += 2) {
long long num = i * 10 + i;
if (num >= m && num <= n && isPrime(num)) {
cout << num << "\n";
found = true;
}
}
// 3. Tạo số đối xứng có >= 3 chữ số
// Sinh nửa đầu (left), tạo số nguyên tố đối xứng, kiểm tra range
for (long long len = 3; len <= 9; len++) {
long long start = 1;
for (int k = 1; k < len / 2; k++) start *= 10;
long long end = start * 10 - 1;
for (long long left = start; left <= end; left++) {
string s = to_string(left);
string rev = s;
reverse(rev.begin(), rev.end());
long long num;
if (len % 2 == 0) {
num = stoll(s + rev);
} else {
num = stoll(s + rev.substr(1));
}
if (num > n) continue; // Optimization: if num > n, larger lefts will also be > n
if (num >= m && isPrime(num)) {
cout << num << "\n";
found = true;
}
}
}
if (!found) cout << 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
- Time Complexity: O(10^(D/2) * sqrt(N)) (D là số chữ số tối đa)
- Space Complexity: O(1)
Thay vì kiểm tra tất cả các số trong khoảng [m, n], ta chỉ sinh ra các số đối xứng và kiểm tra xem chúng có phải là số nguyên tố hay không. Số đối xứng được tạo ra bằng cách lấy một nửa số (hoặc nửa số + 1 chữ số ở giữa), sau đó nối với phần đối xứng của nó. Số lượng số đối xứng nhỏ hơn rất nhiều so với số lượng số tự nhiên (ví dụ: chỉ có khoảng 20,000 số đối xứng <= 10^8).
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O((n-m) * sqrt(n) + D * log n) ~ O(n * sqrt(n)) | O(1) | Brute Force (Kiểm tra từng số) |
| 2 | O(N log log N + (n-m) * log n) | O(N) ~ 100MB | Sàng Eratosthenes (Pre-compute Primes) |
| 3 | O(10^(D/2) * sqrt(N)) (D là số chữ số tối đa) | O(1) | Tạo số đối xứng (Digit Generation) |
Bài học kinh nghiệm
- Số lượng số đối xứng trong khoảng [1, 10^8] rất nhỏ (~20,000 số) so với 100 triệu số tự nhiên. Tận dụng đặc điểm này để sinh số đối xứng thay vì sàng lọc.
- Việc kiểm tra tính nguyên tố cho các số lớn tốn thời gian. Kết hợp với sàng Eratosthenes hoặc chỉ kiểm tra trên các số được sinh ra là chìa khóa để tối ưu.
- Số đối xứng có số chữ số chẵn phải chia hết cho 11 (trừ 11). Do đó, các số đối xứng chẵn chữ số lớn hơn 11 đều không phải số nguyên tố.
Lỗi thường gặp
- Quên xử lý trường hợp không tìm thấy số nào (phải in ra 0).
- Kiểm tra số nguyên tố sai (ví dụ: lặp đến n thay vì sqrt(n), hoặc không xử lý các trường hợp cơ bản như 2, 3).
- Sử dụng kiểu dữ liệu int cho các biến số lớn (n có thể lên tới 10^8, nhưng khi tạo số đối xứng hoặc tính toán có thể vượt quá giới hạn của int, nên dùng long long).
- Sàng Eratosthenes quá tốn bộ nhớ nếu khai báo mảng bool hoặc int trên stack (nên dùng vector hoặc static/global array).
Bình luận