I have to build a program in C who reads a n integer number and n pairs of 2 integers numbers.The program should display those pairs of numbers I read whose greatest common divisor is a prime number.
My problem is that I get stuck at the code for reading the pairs of numbers and how to print them if they respect the condition. My code:
#include <stdio.h>
// find the gcd between 2 numbers
int gcd(int a, int b)
{
if(a==0)
return b;
while(b!=0)
{
if(a>b)
{
a=a-b;
}
else
{
b=b-a;
}
}
return a;
}
// check if a number is prime
int prime(int a)
{
int i;
if(a<2)
return 0;
for (i=2;i<=a-1;i++)
{
if (a%i==0)
return 0;
}
return 1;
}
int main()
{
int n,i;
int x,y,result;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d%d",&x,&y);
printf("(%d,%d)",x,y);
result=gcd(x,y);
}
for(i=0;i<n;i++)
{
if(prime(result)==1)
printf("(%d,%d)",x,y);
}
return 0;
}
My problem is in main function where I get stuck at this part of reading and displaying the pairs.For example if I enter n=3 and I read the following pairs: (12,20),(3,6) and (14,21) the program should display (3,6) and (14,21) because gcd of these pairs is a prime number.
It is unclear what you are asking.
you maybe are asking how to loop n times (3 here) to store the pairs?
do you know arrays yet?
unrelated but if a number is not prime, then it has a factor <= its square root.
the square root of a number is significantly smaller than n-1. consider 1 million, its sqrt is 1000. The difference between 1000 loops and 999999 loops is considerable.
there are better ways to get primes, but that alone is a big help. The return statement makes this have no effect here, so its not worth changing it, just be aware of the math.