#include<bits/stdc++.h>
using namespace std;
int main()
{
 string n;
 cin>>n;
 for (int i=0;i<n.length();i++)
 {
  if (n[i]=='2'||n[i]=='3'||n[i]=='5'||n[i]=='7')
  {
   continue;
  }
  else {
   cout<<"ko phai so dep";
   exit(0);
  }
 }
 cout<<"so dep";
}

SOL:

• Gọi $prime(n)$ là hàm kiểm tra số nguyên tố

• Gọi $sumDigits(n)$ là hàm tính tổng các chữ số của $n$

• Kiểm tra nếu $prime(sumDigits(n))=true\Rightarrow n$ là số nguyên tố

• Độ phức tạp thời gian của cách này là $O(n)$

Code:

#include <bits/stdc++.h>
using namespace std;

bool prime(int n) {
    if(n<2) return false;
    for(int i=2; i<=sqrt(n); i++) {
        if(n%i==0) {
            return false;
        }
    }
    return true;
}

int sumDigits(int n) {
    if(n<10) return n;
    else return (n%10)+sumDigits(n/10);
}

int main() {
    int n;
    cin >> n;
    if(prime(sumDigits(n))) {
        cout << "YES" << "\n";
    } else {
        cout << "NO" << "\n";
    }
}