Ta định nghĩa n là số siêu nguyên tố nếu n là một số nguyên tố và khi liên tục b…
Dữ liệu: Dòng đầu tiên ghi số nguyên dương .
Kết quả: In ra YES nếu n là số siêu nguyên tố, NO nếu n ngược lại.
Codeblock
Mục tiêu bài học:
* Hiểu rõ định nghĩa số siêu nguyên tố.
* Biết cách kiểm tra một số có phải là số nguyên tố hay không.
* Vận dụng kiến thức để viết chương trình kiểm tra số siêu nguyên tố.
Bước 1: Phân tích đề bài và hiểu rõ khái niệm “số siêu nguyên tố”
Đề bài cho chúng ta một định nghĩa rất rõ ràng về số siêu nguyên tố:
* Điều kiện 1: Số đó phải là một số nguyên tố.
* Điều kiện 2: Khi ta liên tục bỏ đi chữ số ở tận cùng bên phải của số đó, các số còn lại cũng phải là số nguyên tố.
* Điều kiện 3: Quá trình bỏ chữ số này diễn ra cho đến khi số chỉ còn lại một chữ số, và số có một chữ số đó cũng phải là số nguyên tố.
Ví dụ: Số 23.
* 23 là số nguyên tố.
* Bỏ chữ số 3 bên phải, ta còn lại 2. 2 cũng là số nguyên tố.
* Vì 2 là số có một chữ số và là số nguyên tố, nên 23 thỏa mãn tất cả các điều kiện và là số siêu nguyên tố.
Ví dụ không phải: Số 413.
* 3 là số nguyên tố.
* 41 là số nguyên tố.
* 4 là số có một chữ số. Nhưng 4 không phải là số nguyên tố (vì 4 chia hết cho 2).
* Do đó, 413 không phải là số siêu nguyên tố.
Như vậy, để kiểm tra một số n có phải là số siêu nguyên tố hay không, chúng ta cần thực hiện hai công việc chính:
1. Kiểm tra tính nguyên tố của chính số n.
2. Thực hiện phép “bỏ chữ số bên phải” và kiểm tra tính nguyên tố của các số tạo thành cho đến khi chỉ còn một chữ số.
Bước 2: Nhắc lại kiến thức về số nguyên tố
Các em còn nhớ thế nào là số nguyên tố không?
Số nguyên tố là số tự nhiên lớn hơn 1, chỉ có hai ước số dương là 1 và chính nó.
Ví dụ: 2, 3, 5, 7, 11, 13, …
Để kiểm tra xem một số nguyên dương \(x\) có phải là số nguyên tố hay không, ta có thể làm như sau:
* Nếu \(x\) < 2, thì \(x\) không phải là số nguyên tố.
* Nếu \(x\) = 2, thì \(x\) là số nguyên tố.
* Nếu \(x\) > 2 và \(x\) chẵn, thì \(x\) không phải là số nguyên tố.
* Nếu \(x\) > 2 và \(x\) lẻ, ta sẽ kiểm tra xem \(x\) có chia hết cho bất kỳ số lẻ nào từ 3 cho đến căn bậc hai của \(x\) (bao gồm cả căn bậc hai của \(x\)) hay không. Nếu \(x\) chia hết cho bất kỳ số nào trong khoảng này, thì \(x\) không phải là số nguyên tố. Ngược lại, nếu \(x\) không chia hết cho bất kỳ số nào trong khoảng này, thì \(x\) là số nguyên tố.
Để tiện cho việc lập trình, chúng ta sẽ viết một hàm để kiểm tra tính nguyên tố.
Bước 3: Xây dựng hàm kiểm tra tính nguyên tố
Chúng ta sẽ viết một hàm có tên \(is_prime(num)\) trả về \(True\) nếu \(num\) là số nguyên tố, và \(False\) nếu ngược lại.
python
def is_prime(num):
if num < 2:
return False
if num == 2:
return True
if num % 2 == 0:
return False
# Kiểm tra các ước số lẻ từ 3 đến căn bậc hai của num
# Ta chỉ cần kiểm tra đến phần nguyên của căn bậc hai
i = 3
while i * i <= num:
if num % i == 0:
return False
i += 2 # Chỉ kiểm tra các số lẻ
return True
Bước 4: Xây dựng logic kiểm tra số siêu nguyên tố
Bây giờ, chúng ta sẽ viết một hàm \(is_super_prime(n)\) để kiểm tra xem số \(n\) có phải là số siêu nguyên tố hay không.
* Đầu tiên, ta cần kiểm tra xem chính số \(n\) có phải là số nguyên tố không bằng cách gọi hàm \(is_prime(n)\). Nếu không phải, trả về \(False\) ngay.
* Nếu \(n\) là số nguyên tố, ta sẽ bắt đầu quá trình “cắt bỏ chữ số bên phải”. Chúng ta có thể làm điều này bằng cách sử dụng phép chia lấy phần nguyên cho 10. Ví dụ: 413 // 10 = 41. 41 // 10 = 4.
* Ta sẽ dùng một vòng lặp \(while\) để tiếp tục quá trình này miễn là số còn lại vẫn còn nhiều hơn một chữ số.
* Trong mỗi lần lặp, ta sẽ lấy số hiện tại, bỏ đi chữ số bên phải, và kiểm tra xem số mới này có phải là số nguyên tố không. Nếu bất kỳ số nào trong chuỗi này không phải là số nguyên tố, ta sẽ trả về \(False\).
* Nếu vòng lặp kết thúc (tức là chúng ta đã kiểm tra đến số có một chữ số) và tất cả các số đều là số nguyên tố, thì \(n\) là số siêu nguyên tố và ta trả về \(True\).
python
def is_super_prime(n):
temp_n = n
while temp_n > 0:
if not is_prime(temp_n):
return False
temp_n = temp_n // 10 # Bỏ đi chữ số bên phải
return True
Bước 5: Viết chương trình chính
Chương trình chính sẽ bao gồm:
* Nhập số nguyên dương \(n\) từ người dùng.
* Gọi hàm \(is_super_prime(n)\) để kiểm tra.
* In ra “YES” nếu kết quả là \(True\), “NO” nếu kết quả là \(False\).
python
# Hàm kiểm tra số nguyên tố (như đã định nghĩa ở Bước 3)
def is_prime(num):
if num < 2:
return False
if num == 2:
return True
if num % 2 == 0:
return False
i = 3
while i * i <= num:
if num % i == 0:
return False
i += 2
return True
# Hàm kiểm tra số siêu nguyên tố (như đã định nghĩa ở Bước 4)
def is_super_prime(n):
temp_n = n
while temp_n > 0:
if not is_prime(temp_n):
return False
temp_n = temp_n // 10
return True
# Chương trình chính
n = int(input())
if is_super_prime(n):
print(“YES”)
else:
print(“NO”)
Giải thích thêm về cách lấy số khi bỏ chữ số bên phải:
Phép toán \(//\) trong Python là phép chia lấy phần nguyên.
Ví dụ:
\(413 // 10\) sẽ cho kết quả là \(41\).
\(41 // 10\) sẽ cho kết quả là \(4\).
\(4 // 10\) sẽ cho kết quả là \(0\).
Vòng lặp \(while temp_n > 0:\) sẽ đảm bảo chúng ta tiếp tục kiểm tra cho đến khi số trở thành 0. Tuy nhiên, logic bên trong vòng lặp đã xử lý việc kiểm tra số có 1 chữ số (khi \(temp_n\) chỉ còn là 2, 3, 5, 7,…). Khi \(temp_n\) trở thành số có 1 chữ số, ví dụ \(temp_n = 7\), ta gọi \(is_prime(7)\) là đúng. Sau đó, \(temp_n = 7 // 10\) sẽ gán \(temp_n = 0\). Vòng lặp sẽ kết thúc. Nếu tất cả các bước trước đó đều trả về \(True\), thì hàm \(is_super_prime\) sẽ trả về \(True\).
Ví dụ minh họa chạy chương trình:
Giả sử nhập vào \(n = 23\).
1. \(is_super_prime(23)\) được gọi.
2. \(temp_n = 23\).
3. Vòng lặp \(while temp_n > 0\) bắt đầu.
4. Kiểm tra \(is_prime(23)\). Hàm \(is_prime(23)\) trả về \(True\).
5. \(temp_n\) được cập nhật: \(temp_n = 23 // 10 = 2\).
6. Lần lặp tiếp theo của \(while temp_n > 0\) (\(2 > 0\)).
7. Kiểm tra \(is_prime(2)\). Hàm \(is_prime(2)\) trả về \(True\).
8. \(temp_n\) được cập nhật: \(temp_n = 2 // 10 = 0\).
9. Lần lặp tiếp theo của \(while temp_n > 0\) (\(0 > 0\) là \(False\)). Vòng lặp kết thúc.
10. Hàm \(is_super_prime\) trả về \(True\).
11. Chương trình chính in ra “YES”.
Giả sử nhập vào \(n = 413\).
1. \(is_super_prime(413)\) được gọi.
2. \(temp_n = 413\).
3. Vòng lặp \(while temp_n > 0\) bắt đầu.
4. Kiểm tra \(is_prime(413)\). Hàm \(is_prime(413)\) trả về \(False\) (vì 413 = 3 * 137.7… hoặc có thể dùng máy tính kiểm tra, 413 không phải số nguyên tố).
5. Hàm \(is_super_prime\) trả về \(False\).
6. Chương trình chính in ra “NO”.
Giả sử nhập vào \(n = 41\).
1. \(is_super_prime(41)\) được gọi.
2. \(temp_n = 41\).
3. Vòng lặp \(while temp_n > 0\) bắt đầu.
4. Kiểm tra \(is_prime(41)\). Hàm \(is_prime(41)\) trả về \(True\).
5. \(temp_n\) được cập nhật: \(temp_n = 41 // 10 = 4\).
6. Lần lặp tiếp theo của \(while temp_n > 0\) (\(4 > 0\)).
7. Kiểm tra \(is_prime(4)\). Hàm \(is_prime(4)\) trả về \(False\).
8. Hàm \(is_super_prime\) trả về \(False\).
9. Chương trình chính in ra “NO”.
Kết luận:
Chúng ta đã cùng nhau phân tích đề bài, ôn lại kiến thức về số nguyên tố, xây dựng các hàm cần thiết và viết chương trình hoàn chỉnh để giải quyết bài toán số siêu nguyên tố. Các em hãy tự mình thực hành gõ lại code và thử với các trường hợp khác nhau nhé! Nếu có thắc mắc gì, đừng ngần ngại hỏi cô giáo. Chúc các em học tốt!
#include <iostream>
#include <math.h>
#define ll long long
using namespace std;
bool prime(ll n) {
for (ll i=2; i<=sqrt(n); i++) if (n%i==0) return false;
return n>=2;
}
int main() {
ll n;
cin >> n;
while (prime(n)) {
n/=10;
}
if (n==0) cout << “YES”;
else cout << “NO”;
}
#include <bits/stdc++.h>
#define ll long long
#define fr ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const long long N=1e2+5,N1=1e3+5,N2=1e4+5,N3=1e5+5,N4=1e6+5,N5=1e7+5,mod=1e9+7,maxv=1e9;
bool checkprime(ll n){
if(n<=1){
return false;
}
if(n<=3){
return true;
}
if(n%2==0||n%3==0){
return false;
}
for(ll i=5;i*i<=n;i+=6){
if(n%i==0||n%(i+2)==0){
return false;
}
}
return true;
}
bool check(ll n){
while(checkprime(n)){
n/=10;
}
return checkprime(n);
}
ll n;
int main(){
fr;
//freopen(“.inp”,”r”,stdin);
//freopen(“.out”,”w”,stdout);
cin>>n;
if(check(n)){
cout<<“YES”;
}
else{
cout<<“NO”;
}
}
//code was written by longdegea11