Vizualizare sursă pentru „1902 - DouaMii17”

==Cerința==

Primele 2017 numere naturale, având fiecare exact 2017 divizori naturali, s-au gândit la început de nou an să-şi pună divizorii împreună, în ordine crescătoare, astfel se vor amesteca şi vor mai socializa şi ei în mod democratic. Marele conducător KWI s-a gândit să bage zâzanie între ei şi a început să le pună n întrebări de genul “-Domnule x, faci cumva parte din societatea secretă a divizorilor celor 2017 numere cu câte 2017 divizori?”. Să sperăm că până în anul 2017 va primi toate răspunsurile şi toată lumea va fi fericită.
== Date de intrare ==

Fișierul de intrare '''douamii17.in''' conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații, pentru care trebuie să verificăm dacă se află în şirul divizorilor primelor 2017 numere naturale care au exact 2017 divizori fiecare.

== Date de ieșire ==

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect." Fișierul de ieșire '''douamii17.out''' va conține pe linia i, pentru fiecare i de la 1 la n, 1 dacă al i-lea număr de pe linia a doua a fişierului de intrare se află în şirul divizorilor şi 0 altfel.

În cazul în care datele nu respectă restricțiile, se va afișa: "Datele nu corespund restricțiilor impuse.".
== Restricţii şi precizări ==
*1 ≤ n ≤ 1.000.000
*numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât '''500.000.000'''

== Exemple ==
===Exemplul 1===
; ''douamii17.in''
:5
:1 2 18 23 9
; ''ecran''
:Datele sunt introduse corect.
; ''douamii17.out''
:1
:1
:0
:1
:1


===Exemplul 2===
; ''douamii17.in''
:5
:10 20 30 40 50
; ''ecran''
:Datele sunt introduse corect.
; ''douamii17.out''
:0
:0
:0
:0
:0

===Exemplul 3===
; ''douamii17.in''
:3
:-5 1000000000 2000000000
; ''ecran''
:Datele nu corespund restricțiilor impuse.
; ''douamii17.out''
:
<br>


== Rezolvare == 
<syntaxhighlight lang="python" line="1">
# 1902 - DouaMii17
import math

def is_valid(num_count, num_list):
    if num_count < 1 or num_count > 1000000:
        return False
    for num in num_list:
        if num < 1 or num >= 500000000:
            return False
    return True

def calculate_divisors():
    prime_flags = [0] * 20001
    prime_list = []
    divisor_flags = [0] * (500000001)
    prime_count = 0
    current_num = 2
    while prime_count < 2017:
        if prime_flags[current_num] == 0:
            prime_count += 1
            prime_list.append(current_num)
            current_square = current_num * current_num
            while current_square < 20000:
                prime_flags[current_square] = 1
                current_square += current_num
        current_num += 1

    divisor_flags[1] = 1
    for i in range(2017):
        current_prime = prime_list[i]
        while current_prime < 500000000:
            divisor_flags[current_prime] = 1
            current_prime *= prime_list[i]

    return divisor_flags

if __name__ == "__main__":
    with open("douamii17.in") as input_file:
        num_count = int(input_file.readline().strip())
        num_list = list(map(int, input_file.readline().strip().split()))
        if not is_valid(num_count, num_list):
            print("The data does not meet the required restrictions.")
            exit(0)

    divisors = calculate_divisors()

    print("The input data is correct.")
    with open("douamii17.out", "w") as output_file:
        for num in num_list:
            output_file.write(str(divisors[num]) + "\n")

            













</syntaxhighlight>

==Explicatie==

'''is_valid(n, nums)''': Această funcție primește doi parametri, n și nums. Verifică dacă numărul de elemente din lista nums este cel puțin 1 și cel mult 1.000.000 și dacă fiecare element din listă este mai mare decât 0 și mai mic decât 500.000.000. În cazul în care aceste condiții sunt îndeplinite, funcția returnează True, în caz contrar returnează False.

'''calculate_divisors()''': Această funcție calculează șirul de divizori pentru primele 2017 numere naturale care au exact 2017 divizori. 

Folosește două liste, '''b''' și '''p''', pentru a marca numerele prime și numerele prime anterioare din șirul de divizori. După ce lista '''p''' este completată cu primele 2017 numere prime, funcția calculează divizorii pentru fiecare număr prim, înmulțindu-l cu el însuși, apoi cu fiecare număr prim anterioară din șir, până când ajunge la '''500.000.000'''. 

Rezultatul este returnat sub formă de listă, unde fiecare element are valoarea 1 dacă se află în șirul de divizori, sau 0 altfel.

'''main()''': Această funcție este punctul de intrare în program. 

Verifică dacă datele de intrare sunt valide, apoi apelează funcția '''calculate_divisors()''' pentru a obține șirul de divizori. Rezultatul este scris în fișierul '''douamii17.out''' și afișat pe ecran.