sử dụng quay lui in số thỏa mãn các điều kiện

Đề bài:

Hãy viết chương trình liệt kê tất cả các số tự nhiên K thỏa mãn đồng thời những điều kiện dưới đây:

(i)                 K là số có 5 chữ số;

(ii)               K là số nguyên tố;

(iii)             Đảo ngược các chữ số trong của K cũng là một số nguyên tố;

(iv)              Tổng các chữ số của K cũng là một số nguyên tố;

(v)                Mỗi chữ số trong K cũng là những số nguyên tố.

bài giải:

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

int namchuso( int a[]){
 if(a[1] == 0) 
  return 0;
 else 
  return 1;
}

long giatri(int *a , int n){
 long s = 0, t = 1;
 for( int i = n; i >= 1; i--){
  s = s + a[i]*t;
  t = t * 10;
 }
 return s;
}

void xuat( int a[], int n){
 for(int i = 1; i <= n; i++)
  cout << a[i];
 cout << endl;
}

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

bool tong(int a[], int n){
 int tong = 0;
 for(int i = 1; i <= n; i++){
  tong = tong + a[i];
 }
 if(nto(tong))
  return true;
 else 
  return false;
}

bool daongc(int a[], int n){
 long s = giatri(a,n);
 int dao = 0;
 while( s>0 ){
  int t = s %10;
  dao = dao *10 + t;
  s = s / 10;
 }
 if(nto(dao))
  return true;
 else 
  return false;
}

bool tungso(int a[] , int n){
 for(int i = 1; i <= n; i++){
  if(!nto(a[i]))
   return false;
 }
 return true;
}

void thu(int i, int a[],int n ){
 for(int j = 0; j <= 9; j++){
  a[i] = j;
  if( i == n){
   long s = giatri(a,n);
   if(namchuso(a) && daongc(a,n) && nto(s) && tungso(a,n) && tong(a,n))
   xuat(a,n);
  }
  else thu(i+1, a, n);
 }
}
int main(){
 int n;
 int a[1000] = {};
 cout << "nhap vao so chu so ";
 cin >> n;
 thu(1,a,n);
}