LÀM Ở C++ nhé cảm ơn ạ Bài 2 SODEP.CPP Một số nguyên dương được gọi là đẹp nếu tổng bình phương các chữ số của nó (trong dạng biểu diễn thập phân) là một số nguyên tố. Chẳng hạn: Số 12 là số đẹp vì 1² + 2² = 5 là số nguyên tố. Các số đẹp được sắp xếp theo thứ tự tăng dần của giá trị bắt đầu từ 1. Yêu cầu: Cho số nguyên dương N (1 < Ns 10000). Hãy tìm số đẹp thứ n. Dữ liệu vào: Đọc từ file văn bản SODEP.INP gồm một dòng chứa một số nguyên dương N. Dữ liệu ra: Ghi ra file văn bản SODEP.OUT gồm một dòng là kết quả tìm được.

#include <iostream>
#include <vector>
using namespace std;

const int Lim = 1e5;
vector<int> pr;
vector<int> lpf;
void linear_sieve(int n = 500) {
    pr = {2};
    lpf.assign(n + 1, 2);

    for (int x = 3; x <= n; x += 2) {
        if (lpf[x] == 2) pr.push_back(lpf[x] = x);
        for (int i = 1; i < pr.size() && pr[i] <= lpf[x] && pr[i] * x <= n; ++i)
            lpf[pr[i] * x] = pr[i];
    }
}

bool prime(int x) {
    if (x <= 1) return false;
    return lpf[x] == x;
}

int n, sum[Lim + 1], res = 1;
int main() {
    cin >> n;
    linear_sieve();
    for (int i = 1; i <= Lim; ++i) sum[i] = sum[i / 10] + ((i % 10) * (i % 10));
    
    for (int i = 1; n > 0; ++i) {
        if (prime(sum[i])) --n, res = i;
    }
    cout << res;
}