Editing 3311 - Nr Reg

== Enunt ==

Numerele regulate sunt numerele ce au ca factori primi doar numerele 2, 3 și 5. Primele 20 de numere regulate sunt: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36.

== Cerinta ==

Fișierul de intrare nrreg.in conține pe prima linie numărul natural n (n<=10000). Scrieți un program care determină:

*cel de-al n-lea număr regulat, x;
*cel mai mic divizor d al lui x cu proprietatea că p = x / d este pătrat perfect;
*valoarea p.
Programul va scrie în fișierul nrreg.out valorile x d p, separate prin câte spațiu.

Exemplu: dacă n=10, al zecelea număr regulat este x=12; d=3, iar p=4.

== Date de intrare ==

Fișierul de intrare nrreg.txt conține pe prima linie numărul natural n.

== Date de iesire ==

Fișierul de ieșire nrreg.txt va conține pe prima linie numărul x d p, separate prin câte un spațiu.

== Restrictii si precizari ==

*1 ≤ n ≤ 10000
*prin convenție s-a stabilit că numărul 1 face parte din șirul numerelor regulate.

== Exemplul 1 ==
;Intrare
:10
;Iesire
;Datele introduse corespund restrictiilor impuse
:12 3 4

== Exemplul 2 ==
;Intrare
:17
;Iesire
;Datele introduse nu corespund restrictiilor impuse


== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def este_patrat_perfect(numar):
    radacina = int(numar**0.5)
    return radacina * radacina == numar

def gaseste_nr_regulat(n):
    numere_regulate = [1]
    index_2 = index_3 = index_5 = 0

    while len(numere_regulate) < n:
        next_2 = numere_regulate[index_2] * 2
        next_3 = numere_regulate[index_3] * 3
        next_5 = numere_regulate[index_5] * 5

        next_min = min(next_2, next_3, next_5)
        numere_regulate.append(next_min)

        if next_min == next_2:
            index_2 += 1
        if next_min == next_3:
            index_3 += 1
        if next_min == next_5:
            index_5 += 1

    return numere_regulate[-1]

def cel_mai_mic_divizor_patrat_perfect(numar):
    for d in range(2, numar + 1):
        if numar % d == 0 and este_patrat_perfect(numar // d):
            return d

# Citire date de intrare
with open("nrreg.txt", "r") as fin:
    n = int(fin.readline().strip())

# Determinare al n-lea număr regulat
x = gaseste_nr_regulat(n)

# Determinare cel mai mic divizor cu proprietatea cerută
d = cel_mai_mic_divizor_patrat_perfect(x)

# Determinare valoare p
p = x // d

# Scriere rezultat in fisier
with open("nrreg.txt", "w") as fout:
    fout.write(f"{x} {d} {p}")

</syntaxhighlight>

== Explicatie ==

Al zecelea număr regulat este 12; numărul minim care îl divide pe 12 pentru a obține un pătrat perfect este 3 iar pătratul perfect este 4.