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ăspunsuri la întrebare
/*
Complexitatea temporala
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!