Thread: Stuck on lab problem

Hi everyone, I'm taking my first C class this semester, and I'm kind of stuck on this assignment. We need to:

1) Ask the user for two positive integers
2) Compute and print out the largest common prime factor

I am able to get just the the largest common factor, but I'm stuck on how to get the largest *prime* factor. Right now, my code outputs a very large number, and I can't figure out why.

If anyone could offer some advice/help, I would really appreciate it!

Code:

#include<stdio.h>
int main()
{
    int x, y, z;
    printf("Please enter two integers: \n");
    scanf ("%d%d", &x, &y);
    if(check(x) && check(y))
    {
      z = gcd(x, y);
      if(z < 2)
        printf("No common prime factor");
      else
        printf("Greatest Common Prime Factor of %d and %d is: %d\n",x,y,z);
    }
    else
    {
      printf("Negative numbers not allowed!");
    }
    return 0;
}

int gcd(int p, int q)
{
    int r, greater, smaller;
    
    if (p > q) 
      greater = p, smaller = q;
    else 
      greater = q, smaller = p;
    if(smaller == 0)
    {

      if(prime(greater))
      {
        return greater;
      }
      else
      {
    int a;
    for(a = 2; a <= greater; a++)
    {
      if((greater % a) == 0)
      {
        greater /= a;
        a = 1;
      }
    }
   }
  }
    else
      r = gcd(smaller, greater % smaller);

    return r;
}
    
int prime(int greater)
{
  int i, n, prime;
    for(i = 3; i <= greater; i++){
      prime = 1;
      for(n = 2; n <= i - 1; n++){
    if(i % n == 0){
      prime = 0;
    }
   }
  }
    
    return prime;   
}  

int check(int x)
{
  if(x > 0)
    return 1;
  else
    return 0;

}

Originally Posted by quzah

Find the biggest prime number that divides evenly into your source number. Then do that division. Then find the biggest prime that fits into that number. Repeat until done.


Quzah.

The problem is that I have to find the largest prime number that fits into both of the source numbers. Maybe I'm making this more complicated than it really it though.