2913 - Proth Number

Cerinţa

Un număr natural n se numește număr Proth dacă este de forma n=k*2p+1, unde k și p sunt numere naturale, k este impar și k < 2p. Să se scrie un program care citește un număr natural și verifică dacă este număr Proth.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieşire

Programul va afișa pe ecran mesajul DA dacă n este număr Proth, respectiv NU în caz contrar.

Restricții și precizări

• 1 ≤ n ≤ 1.000.000.000

Exemplu

Intrare

25

Ieșire

DA

Rezolvare

def validare_date(n):
    if not 1 <= n <= 1000000000:
        print("Numarul trebuie sa fie intre 1 si 1000000000.")
        return False
    return True

def este_numar_proth(n):
    if not validare_date(n):
        return False

    k = 1
    while k < n:
        p = (n - 1) // (2**k)
        if 2**k * p + 1 == n and p % 2 == 1:
            return True
        k += 1

    return False

n = int(input("Introduceti numarul n: "))
if este_numar_proth(n):
    print("DA")
else:
    print("NU")