258
Cerința
- Un număr natural nenul este
prim
, dacă are exact doi divizori (ex.7
). - Un număr natural nenul se va numi
pătrat prim
, dacă este pătratul unui număr prim (ex.49 = 7 * 7
). - Un număr natural nenul se va numi
aproape prim
, dacă este produsul a două numere prime distincte (ex.10 = 2 * 5
). - Un număr natural nenul ce nu se încadrează în niciuna din cazurile de mai sus, se numeşte
compus
(ex.8=2*2*2
,100=2*2*5*5
).
Se citeşte un număr natural n
. Să se identifice din ce categorie de mai sus face parte.
Date de intrare
Programul citește de la tastatură numărul n
.
Date de ieșire
Programul va afișa pe ecran unul dintre mesajele: prim
, aproape prim
, patrat prim
sau compus
.
Restricții și precizări
1 < n ≤ 2.000.000.000
Exemplu
Intrare
20
Ieșire
compus
Explicație
Numărul 20=2*2*5
, deci este număr compus.
#include <bits/stdc++.h> using namespace std; int prim(int n); int main () { int n; cin >> n; int i = sqrt(n); if (prim(n)==1) cout << "prim"; else if (prim(n)==2) cout << "aproape prim"; else if (i*i==n && prim(i)==1) { cout << "patrat prim"; } else cout << "compus"; return 0; } int prim(int n) { int cnt=0; for (int i = 1 ; i * i <= n; ++i) { if (n%i==0) cnt+=2; if (i*i==n) cnt--; } if (cnt==2) return 1; else if (cnt==4) return 2; else return 0; }
Comentarii