Problema #381-pbinfo
Un număr natural se numește aproape prim dacă poate fi scris ca produs de două numere naturale prime distincte.
Cerinţa
Se citește un număr natural n și apoi n numere naturale. Să se determine cel mai mare număr aproape prim dintre cele date, și de câte ori apare.
Date de intrare
Programul citește de la tastatură numărul n, și apoi n numere naturale.
Date de ieşire
Programul afișează pe ecran numere M și C, separate prin exact un spațiu, reprezentând cel mai mare număr aproape prim dintre cele date și numărul său de apariții.
Restricţii şi precizări
1 ≤ n ≤ 100
cele n numere citite sunt cuprinse între 1 și 1.000.000.000
Exemplu
Intrare
6
35 55 12 6 25 50
Ieșire
55 1
Puteti sa ma ajutati va rog?
Răspunsuri la întrebare
#include <iostream>
using namespace std;
bool prim(int m)
{
if (m==0 || m==1) return false;
if (m==2) return true;
if (m>2)
{
if (m%2==0) return false;
else
{
for (int i=3; i*i<=m; ++i)
if (m%i==0) return false;
}
return true;
}
}
bool apr_prim(int m)
{
for (int i=2; i*i<m; ++i)
{
if (m%i==0)
{
if (prim(i) && prim(m/i)) return true;
}
}
return false;
}
int main()
{
int n, i, num, maxaprim=1, apmax=1;
cin >> n;
for (i=1; i<=n; ++i)
{
cin >> num;
if (apr_prim(num))
{
if (num>maxaprim) { maxaprim=num; apmax=1; }
else
{
if (num==maxaprim) { ++apmax; }
}
}
}
cout << maxaprim << " " << apmax;
return 0;
}