👤
AndrewSon
a fost răspuns

Cerinţa
Se dă un vector cu n numere naturale. Să se determine câte dintre perechile de elemente din vector sunt prime între ele.

Date de intrare
Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spaţii, reprezentând elementele vectorului.

Date de ieşire
Programul afișează pe ecran numărul C, reprezentând valoarea cerută.

Restricţii şi precizări
1 ≤ n ≤ 200
elementele vectorului vor fi cuprinse între 0 și 1000



Exemplu
Intrare

6
51 18 15 28 77 121
Ieșire

9
Explicație
Perechile de elemente prime între ele sunt:
51 28
51 77
51 121
18 77
18 121
15 28
15 77
15 121
28 121

Cu explicatii daca se poate

Răspuns :

Petruccinator

/*

   Complexitatea temporala [tex]n^{2}[/tex]

   std::__gcd este functia ce determina CMMDC

   Numerele sunt prime intre ele daca CMMDC lor este egal cu 1

*/

#include <iostream>

#include <algorithm>

int main() {

   size_t n, *v, c = 0;

   std::cin >> n;

   v = new size_t[n];

   

   for (size_t i = 0; i < n; ++i)

       std::cin >> v[i];

       

   for (size_t j, i = 0; i < n - 1; ++i)

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

           if (std::__gcd(v[i], v[j]) == 1)

               ++c;

   

   std::cout << c;

   delete[] v;

}

Răspuns:

#include <iostream>

using namespace std;

int v[1001];

bool pie(int a, int b)

{

  int i, p=1;

   if (a==1 || b==1) p=1;

   else

   {

        if ((a==2 && b==2)||(a==b)) p=0;

        else

        {

            if (a<b) { int t=a; a=b; b=t;}

            for (i=2;i*i<=a && p; ++i)

               if (a%i==0)

                { if (b%i==0) {p=0;}

                  else if (b%(a/i)==0) p=0; }

        }

   }

  return p;

}

int main()

{

   int n, j, k, C=0;

   cin >> n;

   for (j=1; j<=n; ++j) cin >> v[j];

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

       for (k=j+1; k<=n; ++k)

         if (pie(v[j], v[k])) ++C;

   cout << C << endl;

   return 0;

}

Explicație:

sper să fie clar codul... e de 100, verificat pe pbinfo, problema NumararePIE

Succese!

Alte intrebari