Editing 2148 - ADN (section)

==Rezolvare==
<syntaxhighlight lang="python" line="1">
#2148 ADN
def conditii(n):
    return 1 <= n <= 5_000_000


def ADN(n):
    martieni_adn = {}
    nr_perechi = 0

    # Inițializăm un dicționar cu cheile de la 1 la n și valorile 1
    for i in range(1, n + 1):
        martieni_adn[i] = 1

    # Folosim Ciurul lui Eratostene pentru a calcula factorizarea în numere prime a fiecărui număr de la 2 la n
    for i in range(2, n + 1):
        # Dacă martieni_adn[i] == 1, atunci i este un număr prim
        if martieni_adn[i] == 1:
            # Setăm factorizarea în numere prime a lui martieni_adn[i] să fie pasul i
            martieni_adn[i] = i
            # Folosind algoritmul Ciurului lui Eratostene, marcam toți multiplii lui i cu factorul prim i
            j = 2
            while j * i <= n:
                martieni_adn[i * j] = martieni_adn[i * j] * i
                # Incrementăm j pentru a considera următorul multiplu al lui i
                j += 1

    # Calculăm numărul de perechi de marțieni cu ADN-e distincte
    for i in range(1, n + 1):
        nr_perechi += int(n / martieni_adn[i])

    print(nr_perechi)


if __name__ == "__main__":
    n = int(input())

    if not conditii(n):
        print("Datele de intrare nu corespund restricțiilor impuse.")
    else:
        print("Datele de intrare corespund restricțiilor impuse.")
        ADN(n)

</syntaxhighlight>