3081 - Truncatable Left

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:

Exemplu

Intrare

1223

Ieșire

DA

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.

Rezolvare

def validare_date(numar):
    flag = False
    if numar.isdigit():
        if 0 <= int(numar) <= 1_000_000_000:
            flag = True
    return flag

def is_prime(numar):
    if numar < 2:
        return False
    for i in range(2, int(numar**0.5) + 1):
        if numar % i == 0:
            return False
    return True

def is_left_truncatable_prime(numar):
    while numar > 0:
        if not is_prime(numar):
            return False
        numar = numar % (10 ** (len(str(numar))-1))
    return True

if __name__ == '__main__':
    numar = input("Introduceti un numar natural: ")
    if validare_date(numar):
        print("\nDatele de intrare corespund restricțiilor impuse.\n")
        numar = int(numar)
        if is_left_truncatable_prime(numar):
            print("DA")
        else:
            print("NU")
    else:
        print("Datele de intrare nu corespund restricțiilor impuse.")