Ai giúp em làm bài này với ạ.Em học c++ ạ

Ý tưởng

Ta cần làm 3 việc sau:

- Duyệt tất cả các số từ $1$ đến $n$, với mỗi số, ta:

  + Kiểm tra tổng các chữ số

  + Kiểm tra xem số đó có nguyên tố hay không

Kiểm tra tổng các chữ số

Dễ thấy, ta có thể lấy tổng các chữ số của $n$ bằng cách lấy tổng các chữ số nhận được khi lần lượt lấy $n$ chia dư cho $10$ (tức lấy chữ số cuối cùng) và lấy $n$ chia nguyên cho $10$ (tức bỏ chữ số cuối cùng, chữ số cuối lúc này là chữ số thứ 2 từ phải sang). Ta có thể dùng 1 vòng while cho việc này.

Kiểm tra xem số có nguyên tố hay không

Một cách rất nổi tiếng và cũng rất đơn giản là duyệt các ước của một số $x$ từ $1$ đến $\sqrt{x}$ (mất $\sqrt{x}$ phép tính). Tuy vậy, nếu ta lồng cách này vào 1 vòng for từ $1$ đến $n$ ta sẽ mất lên đến $6 \times 10^8$ phép tính, khó có thể chạy được mà không quá thời gian. Vì vậy, ta cần nghĩ một cách khác.

Ta thấy, do $n \leq 10^6$ nên mỗi số $x$ trong khi duyệt $1 \rightarrow n$ luôn $\leq n \leq 10^6$. Mà do ta cần tìm các số nguyên tố 1 cách thường xuyên nên ta sẽ nghĩ tới cách: duyệt trước $1 \rightarrow n$ rồi lưu các kết quả kiểm tra SNT vào 1 mảng $prime$. Ta lại nghĩ tới một cách "cổ xưa" để làm việc này: đó chính là Sàng Nguyên Tố Eratosthenes. Ta sẽ sàng nguyên tố trước khi vào vòng for để tìm đáp án như trên, việc sàng mất $N log log N$ (tức khoảng $4 \times 10^6$ phép tính, và việc truy xuất số nguyên tố sau đó sẽ không còn tốn thời gian nữa.

Code tham khảo (C++)

#include <bits/stdc++.h>
#define el cout << '\n'
#define f1(i,n) for(ll i=1;i<=n;i++)
#define __file_name ""
using namespace std;
using ll = long long;
const ll maxn = 1e6+5;

int n,h,res;
bool prime[maxn];
vector<int> ans;

int sumdigit(int x){
    // Tong cac chu so
    res = 0;
    while(x > 0){
        res += x % 10;
        x /= 10;
    }
    return res;
}

void Sieve(){
    // Sang nguyen to
    memset(prime,true,sizeof(prime));
    for(int p=2;p*p<=n;p++){
        if(prime[p]){
            for(int i=p*p;i<=n;i+=p)
                prime[i] = false;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    if(__file_name != ""){
        freopen(__file_name ".inp","r",stdin);
        freopen(__file_name ".out","w",stdout);
    }

    cin >> n >> h;
    Sieve();
    f1(i,n){
        if(prime[i] && sumdigit(i) == h){
            ans.push_back(i);
        }
    }
    cout << ans.size();el;
    for(int i: ans) cout << i << '\n';
    return 0;
}