Question

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 și apoi n numere naturale. Să se determine câte dintre ele sunt aproape prime.
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 numărul C, reprezentând câte dintre numerele citite sunt aproape prime.
Restricţii şi precizări
1 ≤ n ≤ 100
cele n numere citite sunt cuprinse între 1 și 1.000.000.000

Answer 1

#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, num, i, c=0;

  cin >> n;

  for (i=1; i<=n; ++i)

  {

      cin >> num;

      if (apr_prim(num)) ++c;

  }

  cout << c;

   return 0;

}