Cerința

Un număr prim se numește trunchiabil-stânga dacă, prin eliminare repetată a primei cifre, toate numerele rezultate sunt prime.

Cerința

Un număr prim se numește trunchiabil-stânga dacă, prin eliminare repetată a primei cifre, toate numerele rezultate sunt prime.
Se dă un număr natural, să se verifice dacă numărul este prim trunchiabil-stânga.

Date de intrare

Programul citește un număr natural nenul n.

Date de ieșire

Programul va afișa DA dacă n este prim trunchiabil-stânga, altfel va afișa NU.

Restricții și precizări

• n este mai mic decât 1.000.000.
• Cel mai mare prim trunchiabil-stânga este 357686312646216567629137.

Exemplu 1:

Intrare

1223

Ieșire

DA

Exemplu 2:

Intrare

263

Ieșire

NU

Explicație

Exemplu 1: 1223 e prim. Eliminăm 1, 223 e prim. Eliminăm 2, 23 e prim. Eliminăm 2, 3 e prim.
Deci, numărul 1223 e prim trunchiabil-stânga.
Exemplu 2: 263 e prim. Eliminăm 2, dar 63 nu e prim.
Deci, 263 nu e prim trunchiabil-stânga.

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

unsigned long long a;
bool ok = true;

int nrcif(unsigned long long a){
    int cnt = 0;
    while(a) cnt ++, a/=10;
    return cnt;
}

unsigned long long sterg(unsigned long long n){
    int a = nrcif(n);
    unsigned long long p = 1;
    while(a){
        p *= 10;
        a--;
    }
    p/=10;
    return n % p;
}

bool prim(unsigned long long n){
    unsigned long long cnt = 1;
    unsigned long long d = 2;
    while(n > 1){
        int p = 0;
        while(n % d == 0)
            n/=d, p++;
        cnt *= p + 1;
        if(cnt > 2)
            return 0;
        d++;
        if(d * d > n)
            d = n;
    }
    if(cnt == 2)
        return 1;
    return 0;
}

int main(){
    cin >> a;
    while(nrcif(a) > 1){
        if(!prim(a))
            ok = false;
        a = sterg(a);
    }
    if(!prim(a))
        ok = false;
    if(ok == true)
        cout << "DA";
    else
        cout << "NU";
    return 0;
}