#570 · Subiectul II · Programare

Cea mai lungă secvență de numere prime consecutive (subprogramul prim)

✓ Rezolvare explicatăBucurești 2020 · nr. 23

Enunț

a) Subprogramul prim primește prin intermediul parametrului a un număr natural cu cel mult 5 cifre și returnează 1 dacă a este număr prim și 0 în caz contrar. Scrieți la calculator definiția completă a subprogramului.

b) Fișierul numere.in conține un șir cu cel puțin unul și cel mult 10⁶ numere naturale cu cel mult 5 cifre fiecare. Se cere scrierea și executarea la calculator a unui program care citește din fișierul numere.in șirul de valori și scrie în fișierul numere.out numărul de elemente conținut de cea mai lungă secvență de numere prime aflate pe poziții consecutive în șirul citit. Dacă există mai multe secvențe cu același număr maxim de elemente, în fișierul numere.out se va scrie numărul acestor secvențe.

⚠️ Ieșirea e ambiguă prin construcția enunțului. Același fișier poate conține o lungime (o singură secvență maximă) sau un număr de secvențe (mai multe). Un 2 în numere.out poate însemna „secvența maximă are 2 elemente” sau „sunt 2 secvențe de lungime maximă”. Rezolvarea respectă enunțul. Enunțul nu spune ce se scrie dacă șirul nu conține niciun număr prim; aici se scrie 0.

Exemple

Date de intrare (`numere.in`)	Date de ieșire (`numere.out`)	Explicații
`3 5 4 9 7 5 11 5 4 1 3 2 3 4`	`4`	O singură secvență maximă: 7 5 11 5
`3 5 4 9 7 5 11 5 4 1 3 2 5 11 4`	`2`	Două secvențe de lungime 4: 7 5 11 5 și 3 2 5 11

Rezolvare

C++

#include <fstream>
using namespace std;

int prim(int a) {
    if (a < 2) return 0;
    for (int d = 2; d * d <= a; d++)
        if (a % d == 0) return 0;
    return 1;
}

int main() {
    ifstream f("numere.in");
    ofstream g("numere.out");
    int x, lung = 0, lmax = 0, nr = 0;
    while (f >> x) {
        if (prim(x)) {
            lung++;
            if (lung > lmax) {        // secventa noua, mai lunga
                lmax = lung;
                nr = 1;
            } else if (lung == lmax)  // inca una de lungime maxima
                nr++;
        } else
            lung = 0;
    }
    if (nr > 1) g << nr;
    else g << lmax;
    return 0;
}

Exersează mai departe

Probleme cu aceeași tehnică

#163ProgramareCele mai mari două numere perfecte dintr-un fișier #169ProgramareNumerele pare dintre primul și ultimul număr prim #176ProgramareNumerele echilibrate dintr-un fișier, în ordinea inversă citirii #177ProgramareNumerele de două cifre dintr-un fișier, distincte și în ordine crescătoare #182ProgramareNumere divizibile cu 10 după eliminarea cifrelor impare #185ProgramareNumerele palindrom situate după primul număr par