#555 · Subiectul II · Programare

Perechi consecutive de numere neprime, dar prime între ele (subprogramele nr_prim și cmmdc)

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

Enunț

a) Subprogramul nr_prim are un singur parametru n, prin care primește un număr natural cu cel mult patru cifre, și returnează 1 dacă n este prim sau 0 altfel. Subprogramul cmmdc are doi parametri prin care primește câte un număr natural nenul cu cel mult patru cifre. Subprogramul returnează cel mai mare divizor comun al celor două numere. Scrieți la calculator definițiile complete ale celor două subprograme.

b) Fișierul numere.in conține pe prima linie cel puțin două și cel mult 10⁶ numere naturale din intervalul [1, 10⁴], separate prin câte un spațiu. Se cere scrierea și executarea la calculator a unui program care să afișeze pe ecran numărul perechilor de numere citite consecutiv din fișier care nu sunt numere prime, dar sunt numere prime între ele.

Exemple

Date de intrare (`numere.in`)	Date de ieșire	Explicații
`35 45 22 11 8 35 256 1000`	`3`	Se numără perechile (45, 22), (8, 35) și (35, 256)

Rezolvare

C++

#include <fstream>
#include <iostream>
using namespace std;

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

int cmmdc(int a, int b) {
    while (b != 0) {          // algoritmul lui Euclid, prin impartiri
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main() {
    ifstream f("numere.in");
    int a, b, c = 0;
    f >> a;
    while (f >> b) {
        if (!nr_prim(a) && !nr_prim(b) && cmmdc(a, b) == 1) c++;
        a = b;                // perechea urmatoare incepe cu b
    }
    cout << c;
    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