CTDL và giải thuật – Số siêu nguyên tố là số

Posted on by mtoplistChuyên mục:Top List

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ới n = 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ằng 30.

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;
}

mtoplist