- Số đẹp thứ 10000 là 50695 nên đặt giới hạn là 1e5 cho tròn :)

- Số có tổng bình phương chữ số lớn nhất: 99999 (`5.9^2 = 405`). Do đó ta sàng trước [1..405]

- Công thức (tính tổng b.p các số từ [1..n]): sum[i] = sum[i / 10] + `(i % 10)^2`

- Code:

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

//--Coder_Bot--///#pragma GCC optimize("O2")//#pragma GCC target("avx,avx2,fma")#include<bits/stdc++.h>using namespace std;
#define el cout <<"\n"#define ll long long#define ld long double#define f0(i,n) for (int i=0;i< n;i++)#define f1(i,n) for (int i=1;i<=n;i++)#define fv(v,u) for (auto v : u)#define fi first#define se second#define maxn 55004#define maxm 1000006#define names "Bot"int MOD = 1e9 + 7;int INF = INT_MAX;
//declareint n;vector <int> dp;//Coding_from_here;bool prime(int n){ for (ll i = 2;i * i <= n;i++) if (n % i == 0) return 0; return n > 1;}int cal(int n){ int res = 0; while (n){ res += (n%10) * (n%10); n/=10; } return res;}void sol(){ for(int i = 2;i<maxn;i++) if (prime(cal(i))) dp.push_back(i);}int main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); sol(); cin >> n; cout << dp[n-1];}//--Code_Of_Life--//