Số siêu nguyên tố - LCOJ: Luyen Code Online

PTIT057 - Số siêu nguyên tố

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Tác giả:

Hieu Nguyen

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift

Ở vương quốc Westeros, có 1 nàng công chúa xinh đẹp đang đến tuổi lấy chồng. Nhưng nhà vua muốn chọn 1 người tài giỏi để có thể cùng ông xây dựng vương quốc. Do đó ông cho 1 bài toán cho các thần dân:

Cho 1 con số nguyên dương ~N~ và những ai có thể đưa ra mọi số siêu nguyên tố bé hơn hoặc bằng ~N~ 1 cách nhanh nhất sẽ trở thành phò mã.

Số siêu nguyên tố là là số nguyên tố mà khi bỏ đi lần lượt một chữ số bên phải thì nó vẫn là số nguyên tố

~VD~: ~233~ là 1 số siêu nguyên tố vì:

~233~ là số nguyên tố
~23~ là số nguyên tố
~2~ là số nguyên tố

với những dữ liệu trên liệu bạn có đủ thông minh để trở thành phò mã không?

Input

Nhập vào 1 số nguyên dương duy nhất ~N~ ~(1 \le N \le 30000)~

Output

In ra màn hình tất cả những số siêu nguyên tố tìm được theo thứ tự tăng dần, mỗi số cách nhau bởi 1 dấu cách
Nếu không tồn tại số nào in ra -1.

Sample

Input #1

Output #1

2 3 5 7

Input #2

Output #2

2 3 5 7 23 29 31 37

Problem source: CLB Lập Trình PTIT

Bình luận

Hãy đọc nội quy trước khi bình luận.

include <iostream>

include <vector>

include <cmath>

using namespace std;

// Hàm kiểm tra số nguyên tố bool isPrime(int n) { if (n <= 1) { return false; } for (int i = 2; i <= sqrt(n); i++) { if (n % i == 0) { return false; } } return true; }

// Hàm kiểm tra số siêu nguyên tố bool isSuperPrime(int n) { // Chuyển số nguyên thành chuỗi để dễ xử lý từng chữ số string str = to_string(n);

// Kiểm tra từng chữ số bên phải
for (int i = str.length(); i >= 1; i--) {
    // Chuyển chuỗi thành số nguyên khi bỏ đi chữ số cuối cùng
    int truncatedNum = stoi(str.substr(0, i));

    // Nếu số này không phải là số nguyên tố, không phải là số siêu nguyên tố
    if (!isPrime(truncatedNum)) {
        return false;
    }
}

return true;

}

int main() { int n; cin >> n;

vector<int> superPrimes;

// Tìm các số siêu nguyên tố từ 2 đến n
for (int i = 2; i <= n; i++) {
    if (isSuperPrime(i)) {
        superPrimes.push_back(i);
    }
}

// In ra kết quả
if (superPrimes.empty()) {
    cout << -1;
} else {
    for (int i = 0; i < superPrimes.size(); i++) {
        cout << superPrimes[i];
        if (i < superPrimes.size() - 1) {
            cout << " ";
        }
    }
}

return 0;

} Chỉ mang tính chất tham khảo vì em đã ac nhưng cmt thì nó bị lỗi nên mn chỉ có thể tham khảo thôi chứ ko cppy nộp và full ac đâu tại web nó bị lỗi phong chữ. Mong mn thông cảm và cho em 1 vote nhé.

-2

taco29 đã bình luận lúc 10, Tháng 12, 2023, 4:57

~~test cuoi la j vay mng~~

-2

taco29 đã bình luận lúc 10, Tháng 12, 2023, 5:00

`