simple GCD, help

S

sathyashrayan

Dear group,
I tryied to impliment a simple GCD algo, just print the common
divisors between two numbers. The simple task I was trying with various
method and till now I could not able to implement. Below is a one try but
various attempts looks nonsensial.
I might be weasting you peoples precious time but, since I an a
self thought lerner i put this in the group for help, thanks.
int main(void)
{
int first, second,i,j, first_rem, first_quot, second_rem,
second_quot, common_div=0;
scanf("%d%d",&i,&j);
do{
for(i = 2 ; i< first ; i++)
{
first_rem = i % first;
first_quot = i / first;
}
for(j = 2 ; j < second ; j++)
{
second_rem = i % second;
second_quot = i / second;
}
if(first_quot == second_quot)
{
common_div = first_quot;
printf("common divisers = %d\n",common_div);
}
}while(first_rem != 0 && second_rem != 0);
return 0;
}
 
S

santosh

sathyashrayan said:
Dear group,
I tryied to impliment a simple GCD algo, just print the common
divisors between two numbers. The simple task I was trying with various
method and till now I could not able to implement. Below is a one try but
various attempts looks nonsensial.
I might be weasting you peoples precious time but, since I an a
self thought lerner i put this in the group for help, thanks.
int main(void)
{
int first, second,i,j, first_rem, first_quot, second_rem,
second_quot, common_div=0;
scanf("%d%d",&i,&j);

Include stdio.h for using scanf() and printf().
do{
for(i = 2 ; i< first ; i++)

At this point first is uninitialised. It might have any garbage value.
Initialise it with a sensible value either when declaring it or
sometime before first using it.

You also overwrite the input from the user which you've stored into i
in the scanf() statement. I think you meant to asign i to first and
then count i up from 2.
{
first_rem = i % first;
first_quot = i / first;
}
for(j = 2 ; j < second ; j++)

Again you're using second uninitialised and you're overwriting your
second input in j.
{
second_rem = i % second;
second_quot = i / second;
}
if(first_quot == second_quot)
{
common_div = first_quot;
printf("common divisers = %d\n",common_div);
}
}while(first_rem != 0 && second_rem != 0);
return 0;
}

Until you fix the mistakes pointed out, we can't proceed further. Your
algorithm is needlessly convolvuted for such a simple problem.
 
S

santosh

sathyashrayan said:
Dear group,
I tryied to impliment a simple GCD algo, just print the common
divisors between two numbers. The simple task I was trying with various
method and till now I could not able to implement. Below is a one try but
various attempts looks nonsensial.
I might be weasting you peoples precious time but, since I an a
self thought lerner i put this in the group for help, thanks.
<snip code>

Here's a quick version I whipped up:

/* gcd00.c */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <errno.h>

unsigned long int get_input(const char *);

int main(void) {
unsigned long int first, second, gcd, found = 0;

first = get_input("first");
second = get_input("second");

for(gcd = (first > second) ? second : first; gcd > 1; gcd--)
if(first % gcd == 0 && second % gcd == 0) { found = 1;
break; }

if(found)
printf("G.C.D. is: %lu\n", gcd);
else
puts("No G.C.D.");

return !found;
}

unsigned long int get_input(const char *num) {
unsigned long int value = 0;
char input[BUFSIZ];

printf("Enter ");
printf(num);
printf(" number: ");
fflush(stdout);

if(fgets(input, BUFSIZ, stdin) == NULL) {
puts("Invalid input.");
exit(EXIT_FAILURE);
}

if(strchr(input, '-') != NULL) {
puts("Input must be a positive number.");
exit(EXIT_FAILURE);
}

errno = 0;
value = strtoul(input, NULL, 0);
if(value == ULONG_MAX && errno == ERANGE) {
puts("Input too large.");
exit(EXIT_FAILURE);
}
if(value < 2) {
puts("Input must be atleast two or more.");
exit(EXIT_FAILURE);
}

return value;
}
/* End gcd00.c */
 
S

santosh

sathyashrayan said:
Dear group,
I tryied to impliment a simple GCD algo, just print the common
divisors between two numbers. The simple task I was trying with various
method and till now I could not able to implement. Below is a one try but
various attempts looks nonsensial.
I might be weasting you peoples precious time but, since I an a
self thought lerner i put this in the group for help, thanks.
<snip>

Two trivial optimisations are to see if the two inputs are equal or if
one is a factor of the other. The problem gets more challenging when
you deal with multiple values.
 
S

Spiros Bousbouras

santosh said:
<snip code>

Here's a quick version I whipped up:

/* gcd00.c */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <errno.h>

unsigned long int get_input(const char *);

int main(void) {
unsigned long int first, second, gcd, found = 0;

first = get_input("first");
second = get_input("second");

for(gcd = (first > second) ? second : first; gcd > 1; gcd--)
if(first % gcd == 0 && second % gcd == 0) { found = 1;
break; }

if(found)
printf("G.C.D. is: %lu\n", gcd);
else
puts("No G.C.D.");

return !found;
}
<SNIP REST OF CODE>

1 is a perfectly legitimate value for the gcd.
Your programme is designed in such a way
as to never print 1 as the gcd. Furthermore
return !found for found==0 is non-portable.
That part is not needed anyway since the gcd
will always exist.
 
S

santosh

Spiros said:
1 is a perfectly legitimate value for the gcd.
Your programme is designed in such a way
as to never print 1 as the gcd.

Umm, you don't really need a program, (or a computer), to figure out
one as a G.C.D. I don't know about you, but I suspect that most people
are interested in G.C.Ds. _other_ than one.
Furthermore
return !found for found==0 is non-portable.

You're quite right. That skipped my mind. I think the return can be
replaced by:
return (found != 0) ? 0 : EXIT_FAILURE;
That part is not needed anyway since the gcd
will always exist.

Not when you ignore one.
 
S

Spiros Bousbouras

santosh said:
Umm, you don't really need a program, (or a computer), to figure out
one as a G.C.D. I don't know about you, but I suspect that most people
are interested in G.C.Ds. _other_ than one.

1 is an obvious common divisor but if the
numbers are large enough it's not obvious
that it is the *greatest* common divisor and
you would need a computer to verify it. I
suspect that people who are looking for the gcd
want to know the value whether it's 1 or larger
than 1.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,904
Latest member
HealthyVisionsCBDPrice

Latest Threads

Top