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ì 12 + 22 = 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: Hãy tìm số đẹp thứ n. Dữ liệu vào: - Một dòng chứa một số nguyên dương n (1 <= n <= 10000). Kết quả: - Ghi ra kết quả tìm được.

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

Để giải bài toán này trên Python,ta có thể tạo một hàm kiểm tra số nguyên tố và một hàm tìm số đẹp thứ n.

Đầu tiên, ta viết một hàm để kiểm tra số nguyên tố:

import math

def is_prime(number):
    if number < 2:
        return False
    for i in range(2, int(math.sqrt(number)) + 1):
        if number % i == 0:
            return False
    return True

Tiếp theo, ta viết một hàm để tìm số đẹp thứ n:

def find_beautiful_number(n):
    count = 0
    number = 1
    
    while count < n:
        digit_sum = sum(int(digit)**2 for digit in str(number))
        if is_prime(digit_sum):
            count += 1
        number += 1
    
    return number - 1

Sau đó, ta có thể sử dụng hàm find_beautiful_number để tìm số đẹp thứ n:

n = int(input("Nhập số đẹp thứ n: "))
result = find_beautiful_number(n)
print("Số đẹp thứ", n, "là:", result)

Chương trình sẽ yêu cầu bạn nhập số đẹp thứ n và sau đó tính và in ra số đẹp thứ n tương ứng.

Sử dụng thuật toán tương tự với những ngôn ngữ khác để giải bài toán này nhé.