greatest common divisor is a prime number (pairs of numbers problem in C)

Oct 27, 2019 at 5:23pm
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
  #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.
Oct 27, 2019 at 6:19pm
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.
Last edited on Oct 28, 2019 at 3:43pm
Topic archived. No new replies allowed.