Số siêu nguyên tố (SPRIME)
Đề bài
Số siêu nguyên tố là số nguyên tố mà khi bỏ một số tuỳ ý các chữ số bên phải của nó thì phần còn lại vẫn tạo thành một số nguyên tố.
Ví dụ: $7331$ là một số siêu nguyên tố có $4$ chữ số vì $733$, $73$, $7$ cũng là các số nguyên tố.
Hiếu tình cờ nhặt được số nguyên dương $n$, và tự hỏi có bao nhiêu số siêu nguyên tố có $n$ chữ số. Bạn hãy giúp Hiếu giải đáp câu hỏi trên nhé!
Dữ liệu vào: số nguyên dương $n$ ($1 \le n \le 10$).
Dữ liệu ra: in ra các số siêu nguyên tố có $n$ chữ số trên cùng $1$ dòng, cách nhau $1$ kí tự trắng.
12 3 5 7Lời mở đầu
Bài này mình được một em học viên hỏi và mình đã hướng dẫn chi tiết cách thức giải quyết cho em ấy. Tin rằng sẽ có giá trị với nhiều bạn nên mình chia sẻ đề bài để các bạn thử sức, kèm theo đó là toàn bộ tin nhắn của mình với em ấy để bạn nào không giải quyết được thì có thể tham khảo nhen. Hi vọng mang đến được giá trị cho các bạn 😇. Bài này các bạn có thể xem đề và nộp tại đây nha:
Link này công khai, bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên LuyenCodeLộ trình lời giải, bấm vào từng phần để nhảy tới:
Vấn đềVì sao xét hết các số có $n$ chữ số bị TLE?
Đầu tiên em ấy cho mình xem code bài làm, đi theo đúng như định nghĩa đề bài: viết hàm kiểm tra số $X$ bất kỳ có phải số nguyên tố không, sau đó duyệt qua toàn bộ các số có $n$ chữ số (ví dụ $n = 4$ thì xét từ 1000 đến 9999). Với mỗi số thì loại bỏ dần từng chữ số bên phải và kiểm tra phần còn lại có còn là số nguyên tố không, nếu tất cả đều thoả thì đó là số siêu nguyên tố. Ví dụ 1234 thì xét 1234, 123, 12, 1.
Nếu làm như cách trên của em thì với $n$ tối đa là 10 như đề bài cho, nghĩa là lặp từ 1 tỷ đến 10 tỷ → lặp 9 tỷ lần. Mình còn chưa tính chi phí với mỗi số phải đi loại bỏ dần bên phải, rồi mỗi số đó còn phải kiểm tra nguyên tố. Chỉ nói riêng việc lặp 9 tỷ lần: máy tính phổ thông 1 giây lặp được khoảng 30 đến 50 triệu lần, tức $(3 \text{ đến } 5) \cdot 10^7$. Cho 1 giây được $5 \cdot 10^7$ đi thì $\frac{9 \cdot 10^9}{5 \cdot 10^7} \approx 200$ giây. Trong khi bài này chỉ cho 20 ms 🤣 tức là $\frac{1}{50}$ giây! Nội việc lặp 9 tỷ lần đã cần ít nhất 200 giây, chưa kể còn đống bước xử lý sau đó, không TLE mới lạ 😝
Bài này không thể nào xét hết toàn bộ các số có $n$ chữ số như thế. Em hãy nghĩ ra một cách khác sao cho số lượng số cần xét giảm đi thật nhiều dựa trên định nghĩa của số này nhé. Phải nói là giảm đi rất rất nhiều, không cần xét hết mà chỉ một số rất ít thôi 😁
Ý tưởngKiểm tra từ số nhỏ, sinh dần từ trái sang phải
Dưới đây là hướng giải mình nói ra luôn sau khi em ấy vẫn chưa giải quyết được.
Giả sử cần liệt kê tất cả các số siêu nguyên tố có 5 chữ số. Số có 5 chữ số sẽ có dạng $\overline{abcde}$, thì nó phải thoả tất cả:
Thì chắc chắn ta sẽ cần một hàm kiểm tra số $X$ bất kỳ có là số nguyên tố không. Vấn đề là $X$ càng lớn thì hàm đó càng phải chạy nhiều và lâu.
Quay lại ví dụ số 23579. Em có nghĩ là cần phải kiểm tra cả số 23579 ngay từ đầu không? Một cách làm thông minh hơn là kiểm tra các số thật nhỏ trước, nếu thoả thì mới đi kiểm tra số lớn hơn, còn không thoả thì khỏi kiểm tra luôn. Với 23579: kiểm tra 2 thoả → kiểm tra tiếp 23 thoả → kiểm tra tiếp 235 không thoả → dừng, khỏi mất công kiểm tra 2357, 23579 làm gì. Hay với số 45793: ngay từ đầu 4 đã không phải số nguyên tố thì dừng luôn, khỏi xét 45, 457, 4579, 45793.
Sinh dần từng tầng
- Đầu tiên tạo danh sách có 4 số: 2, 3, 5, 7 – đây chính là 4 số siêu nguyên tố có 1 chữ số.
- Từ 4 số này sinh ra các số siêu nguyên tố có 2 chữ số bằng cách ghép thêm 1 chữ số vào bên phải. Ta không cần xét chữ số chẵn (0, 2, 4, 6, 8) vì khi đó số mới chia hết cho 2, chắc chắn không phải số nguyên tố. Nên ví dụ với số 2, không cần xét 20, 22, 24, 26, 28 mà chỉ xét với các chữ số lẻ 1, 3, 5, 7, 9: 21, 23, 25, 27, 29 – thằng nào là nguyên tố thì giữ lại.
- Tương tự với 3 xét 31, 33, 35, 37, 39; với 5 xét 51, 53, 55, 57, 59; với 7 xét 71, 73, 75, 77, 79.
- Trong 21, 23, 25, 27, 29 thì 23, 29 thoả → giữ lại để sinh tầng 3 chữ số: từ 23 sinh 231, 233, 235, 237, 239; từ 29 sinh 291, 293, 295, 297, 299...
- Cứ thế sinh liên tục đến khi được các số có đủ $n$ chữ số thì dừng, in ra toàn bộ các số đó.
| Số chữ số | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| Số lượng số siêu nguyên tố | 4 | 9 | 14 | 16 | 15 | 12 | 8 | 5 | 0 | 0 |
Bảng trên cho thấy số lượng cần xét cực kỳ ít: mỗi tầng chỉ có vài chục số, tầng 9 thì không còn số nào (5 số 8 chữ số ghép thêm chữ số nào cũng không ra số nguyên tố) nên tầng 10 cũng rỗng luôn.
Minh hoạCây sinh số siêu nguyên tố
Em nhập $n$ (từ 1 đến 6) rồi bấm Tiếp để xem mỗi số ở tầng trước được ghép thêm 1, 3, 5, 7, 9 như thế nào, số nào là nguyên tố thì được giữ lại cho tầng sau:
CodeHai hàng đợi q, q2 – sinh theo tầng
Source code giải quyết theo tư tưởng mình đã trình bày ở trên và cũng đã nộp thành công trên web, các bạn xem để hiểu rõ hơn. Hàng đợi q chứa các số siêu nguyên tố của tầng hiện tại, còn q2 dùng để chứa các số của tầng kế tiếp; xử lý xong một tầng thì gán q = q2 và làm rỗng q2, biến cnt đếm số chữ số hiện có:
#include <bits/stdc++.h>
using namespace std;
bool isPrime(long long x){
for(long long i = 2; i * i <= x; i++){
if(x % i == 0){
return false;
}
}
return x >= 2;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
long long n;
cin >> n;
queue<long long> q, q2;
q.push(2LL);
q.push(3LL);
q.push(5LL);
q.push(7LL);
long long cnt = 1;
while(cnt < n){
while(!q.empty()){
long long x = q.front();
q.pop();
if(isPrime(x * 10 + 1)){
q2.push(x * 10 + 1);
}
if(isPrime(x * 10 + 3)){
q2.push(x * 10 + 3);
}
if(isPrime(x * 10 + 5)){
q2.push(x * 10 + 5);
}
if(isPrime(x * 10 + 7)){
q2.push(x * 10 + 7);
}
if(isPrime(x * 10 + 9)){
q2.push(x * 10 + 9);
}
}
q = q2;
queue<long long> q_empty;
swap(q2, q_empty);
cnt++;
}
while(!q.empty()){
cout << q.front() << " ";
q.pop();
}
return 0;
}from collections import deque
import sys
input = sys.stdin.readline
def is_prime(x):
if x < 2:
return False
for i in range(2, int(x**0.5) + 1):
if x % i == 0:
return False
return True
n = int(input())
q = deque([2, 3, 5, 7])
q2 = deque()
cnt = 1
while cnt < n:
while q:
x = q.popleft()
for d in [1, 3, 5, 7, 9]:
new_num = x * 10 + d
if is_prime(new_num):
q2.append(new_num)
q = q2
q2 = deque()
cnt += 1
for num in q:
print(num, end=' ')Đánh giá độ phức tạp: cả bài chỉ có 83 số siêu nguyên tố (từ 1 đến 8 chữ số), nên tổng số lần gọi isPrime chỉ khoảng $5 \times 83 \approx 400$ lần, mỗi lần tối đa $\sqrt{X} \le 10^5$ vòng lặp. Thực tế phần lớn số bị loại ngay ở vài ước nhỏ đầu tiên, nên toàn bài chạy nhanh hơn ngưỡng $10^6$ rất nhiều.