CTDL và giải thuật - Số siêu nguyên tố là số
Số siêu nguyên tố là số:
- Bản thân nó là số nguyên tố.
- Khi xóa đi lần lượt các chữ số sau cùng của nó, thì số mới vẫn là số nguyên tố.
Ví dụ 2393
là số siêu nguyên tố vì 2393
, 239
, 23
, 2
là số nguyên tố.
Cho một số n
, hãy đưa số dãy số siêu nguyên tố nhỏ hơn hoặc bằng n
, các số đã được sắp xếp tăng dần.
Ví dụ:
- Test mẫu 1:
Input Output 30
2 3 5 7 23 29
Vớin = 30
thìsuperPrimeNumber(n) = [2, 3, 5, 7, 23, 29]
;
Vì các số2
,3
,5
,7
,23
và29
đều là số siêu nguyên tố và nhỏ hơn hoặc bằng30
.
Hướng dẫn bài tập.
Dùng phương pháp sinh, nếu x
đã là số siêu nguyên tố thì ta sẽ lần lượt thêm các số tử 1
đến 9
vào cuối x (x*10 + i)
, rồi kiểm tra xem nó có còn là số siêu nguyên tố hay không. Nếu là số nguyên tố thì lưu nó vào queue.
Code mẫu:
Ngôn ngữ C++:
#include<iostream>
#include<queue>
#include<math.h>
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;
}
int main(){
queue<int> q;
int n;
cin >> n;
for (int i = 2; i <= n, i < 10; i++){
if (isPrime(i)){
q.push(i);
}
}
while (!q.empty()){
for (int i = 1; i <= 9; i++){
int k = q.front()*10 + i;
if ( k <= n && isPrime(k)){
q.push(q.front()*10 + i);
}
}
cout << q.front() << " ";
q.pop();
}
return 0;
}