[Cpp-STL] Queue – SuperPrimeNumber

Bài tập.

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 sắp xếp tăng dần.

Ví dụ:

• 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.

Dùng phương pháp sinh, nếu x đã là số siêu nguyên tố thì 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.

Code mẫu:

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;
}
std::vector<int> superPrimeNumber(int n)
{
    queue<int> q;
    vector<int> v;
    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);
            }
        }
        v.push_back(q.front());
        q.pop();
    }

    return v;
}