Question

Cerinţa

Se citește un număr natural n, n>1. Să se determine câte perechi (a,b) , 1 ≤ a ≤ b ≤ n de numere naturale sunt prime între ele,
Date de intrare

Programul citește de la tastatură numărul n
Date de ieşire

Programul afișează pe ecran numărul C, reprezentând valoarea dorită.
Restricţii şi precizări

1 < n ≤ 1000


Exemplu

Intrare

6

Ieșire

12

depasesc limita de timp.
Ce sa fac?
Dau coroana!!!!


#include

using namespace std;

int prim(int a,int b)
{
int d;
if(a==1)
return 1;
if(a return 0;
if(a!=1)
if(a%b==0)
return 0;
for(d=2;d<=b;d++)
{
if((a%d==0)&&(b%d==0))
return 0;
}
return 1;
}

int main()
{
int n,a,b,ap=0;
cin>>n;
for(a=1;a<=n;a++)
{
for(b=1;b<=n;b++)
{
if(prim(a,b))
ap++;
}
}
cout< return 0;
}

Answer 1

Programul tau nu se compileaza pentru ca ai multe greseli la scriere.
Doua numere sunt prime intre ele cand cel mai mare divizor comun al lui a si b
este egal cu 1; CMMDC(a,b)==1;

#include<iostream>

using namespace std;

int cmmdc(int a,int b)
  { 
    int r=a%b;
    while(r!=0)
    {
      a=b;
      b=r;
     r=a%b;
   }
  return b;
 }

int main()
 {
   int n,a,b,c;
   cin>>n;
  c=0;
  for(a=1;a<n;a++)
   for(b=a;b<=n;b++)
    if(cmmdc(a,b)==1)
    c++; 
  cout<<c;
}