2327 - prim997

Sursa: - prim997

---

Cerinţa

Se dau n numere naturale. Pentru fiecare număr k dat, să se afle cea mai lungă secvenţă de numere naturale consecutive din şirul 1,2,3,...,k, astfel încât orice număr din secvenţă să nu fie prim.

Date de intrare

Fișierul de intrare prim997.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt corecte.", iar apoi in fișierul de ieșire prim997.out va conține pe linia i, primul număr din secvenţă şi lungimea secvenţei, pentru cel de-al i-lea număr de pe linia a doua a fişierului de intrare. În caz contrar, se va afișa pe ecran: "Datele nu sunt comform restricțiilor impuse.".

Restricţii şi precizări

• 1 ≤ n ≤ 100.000
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 10.000.000
• dacă sunt mai multe secvenţe de lungime maximă cu numere consecutive neprime, se va afişa cea cu primul număr din secvenţă minim

Exemple

Exemplul 1

prim997.in

3

4 11 30

Ieșire

Datele sunt corecte.

prim997.out

1 1

8 3

24 5

Exemplul 2

prim997.in

4

19 23 410 421

Ieșire

Datele sunt corecte.

prim997.out

8 3

8 3

114 3

114 3

Exemplul 3

prim997.in

2

314441 41241241

Ieșire

Datele nu sunt comform restricțiilor impuse.

Rezolvare

#2327 prim997


def este_prim(n):
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True


def prim997(nums, n):
    with open("prim997.out", "w") as f:
        for k in nums:
            max_len = 0
            start_num = 1
            current_len = 0
            for i in range(1, k+1):
                if not este_prim(i):
                    current_len += 1
                else:
                    if current_len > max_len:
                        max_len = current_len
                        start_num = i - current_len
                    current_len = 0
            if current_len > max_len:
                max_len = current_len
                start_num = k - current_len + 1
            f.write(f"{start_num} {max_len}\n")


def conform_restrictiilor():
    with open('prim997.in') as f:
        n = int(f.readline())
        vector = list(map(int, f.read().split()))
    if n > 100000:
        print("Datele nu sunt conform restricțiilor impuse.")
        exit()
    for x in vector:
        if x > 10000000:
            print("Datele nu sunt conform restricțiilor impuse.")
            exit()
    print("Datele sunt corecte.")
    return n, vector


if __name__ == '__main__':
    n, vector = conform_restrictiilor()
    prim997(vector,n)

Explicaţie cod

Funcția este_prim(n) primește un număr întreg n și returnează True dacă n este un număr prim, iar False altfel. Algoritmul de verificare a numărului prim verifică dacă n este mai mic decât 2 și dacă este divizibil cu oricare dintre numerele din intervalul [2, sqrt(n)]. Funcția prim997(nums, n) primește o listă de numere întregi nums și un număr întreg n și determină pentru fiecare număr din lista nums cel mai lung subșir format din numere non-prime consecutive. Pentru fiecare număr din listă, se parcurge intervalul [1, k] și se actualizează variabilele max_len (lungimea maximă a unui subșir de numere non-prime consecutive), start_num (primul număr din cel mai lung subșir de numere non-prime consecutive) și current_len (lungimea curentă a unui subșir de numere non-prime consecutive) în funcție de starea curentă a numărului verificat. La final, se scriu în fișierul prim997.out valorile găsite pentru fiecare număr din lista nums. Funcția conform_restrictiilor() citește din fișierul prim997.in un număr întreg n și o listă de numere întregi vector și verifică dacă acestea respectă restricțiile impuse (n ≤ 10^5, valoarea fiecărui element din vector ≤ 10^7). Dacă datele sunt conforme, funcția returnează cele două variabile citite din fișier.