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

  1. #1
    Registered User
    Join Date
    Oct 2019
    Posts
    4

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

    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:

    Code:
    
    
    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)
            return0;
       for(i=2;i<=a-1;i++)
       {
          if(a%i==0)
            return0;
       }
       return1;
    }
    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);
        }
        return0;
    }

    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.

  2. #2
    Registered User
    Join Date
    Feb 2019
    Posts
    1,078
    This:
    Code:
    scanf( "%d%d", &x, &y );
    Should be this:
    Code:
    scanf( "%d %d", &x, &y );

  3. #3
    Registered User Sir Galahad's Avatar
    Join Date
    Nov 2016
    Location
    The Round Table
    Posts
    277
    Well...scanf() can be a hassle sometimes. Try atoi(fgets(buffer, max, stdin)) in a loop instead? You'd have to enter them on separate lines though.
    Last edited by Sir Galahad; 10-27-2019 at 12:04 PM.

  4. #4
    Registered User
    Join Date
    Feb 2019
    Posts
    1,078
    Quote Originally Posted by Sir Galahad View Post
    Well...scanf() can be a hassle sometimes. Try atoi(fgets(buffer, max, stdin)) in a loop instead? You'd have to enter them on separate lines though.
    So, what will happen if fgets() returns NULL? What will happen if fgets() reads something that it is not a string containing an integer value (it will returns 0 in this case!)?
    I think scanf() is better in this context, but one must check the return value:
    Code:
    if ( scanf( "%d %d", &x, &y ) != 2 ) { ... error handling here ... }
    Last edited by flp1969; 10-27-2019 at 12:42 PM.

  5. #5
    Registered User Sir Galahad's Avatar
    Join Date
    Nov 2016
    Location
    The Round Table
    Posts
    277
    Quote Originally Posted by flp1969 View Post
    So, what will happen if fgets() returns NULL? What will happen if fgets() reads something that it is not a string containing an integer value (it will returns 0 in this case!)?
    I think scanf() is better in this context, but one must check the return value:
    Code:
    if ( scanf( "%d %d", &x, &y ) != 2 ) { ... error handling here ... }

    No you're probably right it's a sloppy solution.
    It's fine to use scanf() just be sure not to leave any unprocessed newlines in the input stream.

    Code:
    puts(scanf("%d %d \n", &x, &y) == 2 ? "success" : "FAILURE");

  6. #6
    Registered User
    Join Date
    Feb 2019
    Posts
    1,078
    Quote Originally Posted by Sir Galahad View Post
    No you're probably right it's a sloppy solution.
    It's fine to use scanf() just be sure not to leave any unprocessed newlines in the input stream.
    That's not how scanf() works... scanf will ignore any character that could be tested with isspace() macro from ctypes.h. scanf() will leave these chars on input stream, as you said, but will ignore them when scanning. If you expect a line with 2 ints, "%d %d" will work just fine (by the way... it works fine as well if these 2 ints are in different lines. ' ' will match a '\n' (both return true with isspace(). It work fine too if your line has more than 2 ints - provided you have an even number of ints).

    Here's a simple test to demonstrate:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    int main( void )
    {
      int a, b; 
    
      while ( scanf( "%d %d", &a, &b ) == 2 )
        printf( "%d %d\n", a, b );
    }
    And here's the input (test.txt):
    Code:
    1
    2 3
    4 5 6
    7 8 9 10
    If you compile and run:
    Code:
    $ cc -o test test.c
    $ ./test < test.txt
    1 2
    3 4
    5 6
    7 8
    9 10

  7. #7
    Registered User
    Join Date
    May 2010
    Posts
    4,633
    Also note that the space between the format specifiers is not necessary, ("%d%d") is adequate.

  8. #8
    Registered User
    Join Date
    Feb 2019
    Posts
    1,078
    Quote Originally Posted by jimblumberg View Post
    Also note that the space between the format specifiers is not necessary, ("%d%d") is adequate.
    What if you have something like this as input (considering 'int' as a signed 32 bits type)?

    2147483649100

    Is this 214748364 and 9100? Or a single invalid 'int' value?

    Using that space will garantee the proper separation from values when scanning.

  9. #9
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    Quote Originally Posted by flp1969 View Post
    Using that space will garantee the proper separation from values when scanning.
    You don't know what you're talking about.
    There's no difference.
    A little inaccuracy saves tons of explanation. - H.H. Munro

  10. #10
    Registered User
    Join Date
    May 2010
    Posts
    4,633
    Is this 214748364 and 9100? Or a single invalid 'int' value?
    It is a single invalid int value.

  11. #11
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,791
    Quote Originally Posted by jimblumberg View Post
    It is a single invalid int value.

    While this is clearly correct (according to the C standard since the inception of ANSI C and the C standard) and it's been an interesting diversion, maybe it'd be good to get back to the OP's problem.

    My question to the OP is this: Why are there two loops in main()?

  12. #12
    Registered User Sir Galahad's Avatar
    Join Date
    Nov 2016
    Location
    The Round Table
    Posts
    277
    Okay so maybe inputing ints isn't so bad, but it still chokes on chars pretty easily:

    Code:
    #include <stdlib.h>
    
    void test(const char* format)
    {
     printf("Format: %s\n", format); 
     char a, b, c, d;
     puts("Enter A and B");
     scanf(format, &a, &b);
     printf("A:%c B:%c\n", a, b);
     puts("Enter C and D");
     scanf(format, &c, &d);
     printf("C:%c D:%c\n", c, d);
    }
    
    int main()
    {
     test("%c%c%*c");
     test("%c%c);
    }
    The "%*c" bit seems to do the trick here.

    But then you still have the problem where if the user enters bad input things could get wonky. If you really want good control over your input stream maybe a better approach would be to use fgets with sscanf.

    Code:
    #include <stdlib.h>
    
    #define MAX 1024
    
    void test(const char* format)
    {
     char input[MAX];
     printf("Format: %s\n", format); 
     char a, b, c, d;
     puts("Enter A and B");
     fgets(input, MAX, stdin);
     sscanf(input, format, &a, &b);
     printf("A:%c B:%c\n", a, b);
     puts("Enter C and D");
     fgets(input, MAX, stdin);
     sscanf(input, format, &c, &d);
     printf("C:%c D:%c\n", c, d);
    }
    
    int main()
    {
     test("%c%c%*c");
     test("%c%c");
    }

  13. #13
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,791
    Why is everyone concentrating on how the integers are being read when that's not even the primary problem with the program?

  14. #14
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    308
    Why is everyone concentrating on how the integers are being read when that's not even the primary problem with the program?
    Lmao

    >
    Code:
    int prime(int a){
       int i;
       if(a<2)
            return0;
       for(i=2;i<=a-1;i++)
       {
          if(a%i==0)
            return0;
       }
       return1;
    }
    


    You don't need to be checking for all numbers till i = a - 1. That's just inefficient.... Obviously, 10 isn't divisible by 9.

    Checking till the square-root of the 'a' will do the job (insert: @flp1969 )

    Beginner level issue: next prime number

  15. #15
    Registered User Sir Galahad's Avatar
    Join Date
    Nov 2016
    Location
    The Round Table
    Posts
    277
    Code:
    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);
        }
        return0;
    }
    The value of `result` in the second loop is a going to be whatever pair was last processed in that first loop.

    That gcd code is also horribly inefficient. Use modulus, not subtraction.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. code for getting the GCD (greatest common divisor)
    By Noobpoint in forum C Programming
    Replies: 1
    Last Post: 03-07-2012, 07:13 AM
  2. The greatest common divisor (GCD) help..
    By damha in forum C Programming
    Replies: 4
    Last Post: 04-09-2011, 05:18 AM
  3. Greatest Common Divisor.....
    By muran_pling in forum C++ Programming
    Replies: 10
    Last Post: 12-18-2006, 05:02 AM
  4. Greatest Common Divisor problem
    By fenixataris182 in forum C++ Programming
    Replies: 8
    Last Post: 07-12-2005, 07:55 PM
  5. Greatest common divisor
    By wiz23 in forum C++ Programming
    Replies: 5
    Last Post: 04-13-2005, 04:50 PM

Tags for this Thread