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ụ, 2 333 là số siêu nguyên tố có 4 chữ số vì 233, 232 cũng là các số nguyên tố.

Bài toán 3. 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ụ, 2 333 là số siêu nguyên tố có 4 chữ số vì 233, 232 cũng là các số nguyên tố.

Cho số nguyên dương N (0 < N < 10), đưa ra các số siêu nguyên tố có N chữ số cùng số lượng của chúng. Ví dụ, với N = 4 có 16 số: 2 333, 2 339, 2 393, 2 399, 2 939, 3 119, 3 137, 3 733, 3 739,3 793,3 797, 5 939, 7 193, 7 331, 7 333, 7 393.


Gợi ý:
#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;

}


Bình luận

Giải bài tập những môn khác