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>