Editing 1112 - Puteri4

== Enunt ==
Nu e un secret pentru nimeni faptul că Mireluş se antrenează în timpul liber cu probleme de algoritmică. De curând a aflat că un număr natural N, pentru care există două numere naturale nenule A şi B (B>1) astfel încât N = A^B, se numeşte putere. Mireluş şi-a propus să determine numărul de puteri din intervalul [X, Y], unde X şi Y sunt numere naturale nenule.

Cum probabil v-aţi imaginat deja, Mireluş nu a reuşit să rezolve această problemă şi a decis să ceară ajutorul Olimpiei D’Info. Pentru a fi sigur că nici ea nu greşeşte, i-a dat un set de intervale şi i-a cerut să determine pentru fiecare interval numărul de puteri corespunzător.

== Cerință ==
Dându-se numărul de intervale T şi pentru fiecare din cele T intervale cele două extremităţi, determinaţi numărul de puteri corespunzător fiecărui interval dat de Mireluş Olimpiei.

== Date de intrare ==
Fișierul de intrare puteri4in.txt conține pe prima linie numărul de intervale T, iar pe fiecare din următoarele T linii câte 2 numere naturale nenule X şi Y, separate prin exact un spaţiu, reprezentând extremităţile intervalelor.

== Date de ieșire ==
Fișierul de ieșire puteri4out.txt va conține T linii. Fiecare linie va conţine numărul de puteri care aparţin intervalului corespunzător din fişierul de intrare.

== Restricții și precizări ==
*1 &les; T &les; 131.
*1 &les; X &les; Y &les; 10^18.
*Intervalul [X, Y] conţine şi numerele X şi Y.
*Pentru 10% din teste Y &les; 5000.
*Pentru alte 25% din teste Y &les; 100 000.
*Pentru alte 20% din teste Y &les; 10 000 000.
== Exemplu 1 ==
;puteri4in.txt
:1
:1 36
;puteri4out.txt
:9
:Datele corespund
<br>
== Exemplu 2 ==
;puteri4in.txt
:0
:0 0
;puteri4out.txt
:Datele nu corespund
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
#1112 - Puteri4
def este_putere(numar):
    # Verifică dacă un număr este putere
    for baza in range(2, int(numar ** 0.5) + 1):
        exponent = 2
        putere = baza ** exponent
        while putere <= numar:
            if putere == numar:
                return True
            exponent += 1
            putere = baza ** exponent
    return False

def numar_puteri_in_interval(X, Y):
    numar_puteri = 1
    for numar in range(X, Y + 1):
        if este_putere(numar):
            numar_puteri += 1
    return numar_puteri

def main():
    try:
        with open("puteri4in.txt", "r") as fin:
            T = int(fin.readline().strip())
            intervale = [list(map(int, fin.readline().strip().split())) for _ in range(T)]
    except FileNotFoundError:
        print("Fișierul puteri4in.txt nu a fost găsit.")
        return
    except ValueError:
        print("Datele din fișierul de intrare nu sunt corecte.")
        return

    try:
        with open("puteri4out.txt", "w") as fout:
            for interval in intervale:
                numar_puteri = numar_puteri_in_interval(interval[0], interval[1])
                fout.write(str(numar_puteri) + "\n")
        print("Datele corespund.")
    except IOError:
        print("Nu s-a putut scrie în fișierul de ieșire.")

if __name__ == "__main__":
    main()


</syntaxhighlight>