Bài toán – Số siêu nguyên tố
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ố.
Nhiệm vụ của bạn là viết chương trình nhập dữ liệu vào là một số nguyên N (0< N <10) và đưa ra kết quả là một số siêu nguyên tố có N chữ số cùng số lượng của chúng.
Thuật toán
Đây là một bài toán liên quan đến kiểm tra số nguyên tố và xử lý chuỗi số. Để giải quyết bài toán này, chúng ta có thể thực hiện các bước sau đây:
Bước 1: Nhập vào số nguyên dương N từ người dùng, đảm bảo N nằm trong khoảng từ 1 đến 9.
Bước 2: Tạo một hàm kiểm tra số nguyên tố để sử dụng sau này trong việc tìm kiếm số siêu nguyên tố. Hàm này sẽ trả về True nếu số đó là số nguyên tố và False nếu không.
Bước 3: Tạo một hàm kiểm tra số siêu nguyên tố. Hàm này sẽ nhận vào một số nguyên dương và kiểm tra xem khi bỏ một số tuỳ ý các chữ số bên phải của nó thì phần còn lại có phải là số nguyên tố hay không.
Bước 4: Sử dụng hai hàm trên để tìm kiếm tất cả các số siêu nguyên tố có N chữ số. Chúng ta có thể duyệt tất cả các số có N chữ số từ 10^(N-1) đến 10^N – 1. Với mỗi số đó, ta kiểm tra xem nó có phải là số siêu nguyên tố hay không và tăng biến đếm nếu đúng.
Bước 5: Đưa ra kết quả số lượng và danh sách các số siêu nguyên tố tìm được.
Cài đặt bài toán với Python
def is_prime(n):
if n < 2:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
def is_superprime(n):
n_str = str(n)
for i in range(len(n_str)):
if not is_prime(int(n_str[i:])):
return False
return True
N = int(input("Nhap vao so nguyen duong N (1 <= N <= 9): "))
count = 0
superprimes = []
for i in range(10**(N-1), 10**N):
if is_superprime(i):
count += 1
superprimes.append(i)
print(f"So luong super nguyen to co {N} chu so la: {count}")
print("Cac so super nguyen to do la: ", superprimes)
Cài đặt bài toán với C++
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
bool isPrime(int n) {
if (n < 2) {
return false;
}
for (int i = 2; i <= sqrt(n); i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
bool isSuperPrime(int n) {
string n_str = to_string(n);
for (int i = 0; i < n_str.size(); i++) {
int suffix = stoi(n_str.substr(i));
if (!isPrime(suffix)) {
return false;
}
}
return true;
}
int main() {
int N;
cout << "Nhap vao so nguyen duong N (1 <= N <= 9): ";
cin >> N;
int count = 0;
vector<int> superprimes;
int lower_bound = pow(10, N-1);
int upper_bound = pow(10, N) - 1;
for (int i = lower_bound; i <= upper_bound; i++) {
if (isSuperPrime(i)) {
count++;
superprimes.push_back(i);
}
}
cout << "So luong super nguyen to co " << N << " chu so la: " << count << endl;
cout << "Cac so super nguyen to do la: ";
for (int i = 0; i < superprimes.size(); i++) {
cout << superprimes[i] << " ";
}
cout << endl;
return 0;
}