Numere1 (clasa a 5-a)
Un număr se numeşte aproape prim dacă se poate scrie ca produs de două numere prime distincte.
De exemplu, 10 este număr aproape prim deoarece 10=2*5 iar 2 şi 5 sunt ambele numere prime, în timp ce 18 nu este număr aproape prim.
Cerinţă
Scrieţi un program care să determine câte numere aproape prime sunt într-un şir de n numere date.
Date de intrare
Fişierul de intrare numere1.in conţine pe prima linie un număr natural n reprezentând numărul de valori din şir. Pe următoarea linie se găsesc, separate prin câte un spaţiu, cele n numere naturale care formează şirul.
Date de ieşire
Fişierul numere1.out va conţine o singură linie pe care va fi scris numărul de numere aproape prime din şirul dat.
in limbajul C va rog si fara vectori.
Răspunsuri la întrebare
Program C (testat Visual Studio):
#include <stdio.h>
//Functie care returneaza 1 daca n este prim, 0 altfel
int este_prim(int n) {
int i;
if (n < 2) return 0;
for (i = 2; i <= n / 2; i++) {
if (n % i == 0)
return 0;
}
return 1;
}
//Functie care returneaza 1 daca n este aproape prim, 0 altfel
int este_aproape(int n) {
if (n < 4) return 0;
int i;
for (i = 2; i < n; i++) {
if (n % i == 0) {
if (este_prim(i) && este_prim(n / i))
return 1;
else
return 0;
}
}
return 0;
}
int main() {
FILE* f = fopen("numere1.in", "r");
int n, citit, i, contor = 0;
//Citeste dimensiunea
fscanf(f, "%d", &n);
//Citeste numerele si verifica cate sunt aproape prime
for (i = 0; i < n; i++) {
fscanf(f, "%d", &citit);
//Daca numarul e aproape prim mareste contorul
if (este_aproape(citit))
contor++;
}
fclose(f);
//Afiseaza rezultat
FILE* g = fopen("numere1.out", "w");
fprintf(g, "%d", contor);
fclose(g);
return 0;
}
Explicatie :
Pentru fiecare numar citit n verificam daca este aproape prim. Facem acest lucru cautand primul divizor i al numarului. Daca i si n/i sunt prime atunci numarul dat este aproape prim. Daca unul din ele nu sunt prime atunci numarul dat nu este aproape prim. Daca nu gasim divizor atunci numarul e prim, caz in care nu este aproape prim.
return 1;
else
return 0;