Data Structures using java Your code must be well formatted and commented. While
ID: 672047 • Letter: D
Question
Data Structures using java
Your code must be well formatted and commented. While marks will not be assigned for properly formatting and commenting your code, All programs must include the “Essential Features of Program Documentation” (page 122). Details are included throughout Chapter 2 on best practices for documentation.
Q) Euclid's Algorithm is a well-known algorithm for computing the greatest common divisor (GCD) of two numbers. The algorithm is based on the observation that, if r is the remainder when a is divided by b, then the common divisors of a and b are the same as the common divisors of b and r. Thus we can use the equation to successively reduce the problem of computing a GCD to the problem of computing the GCD of smaller and smaller pairs of integers. GCD (a, b) = GCD (b, r) For example, GCD (36, 20) = GCD (20, 16) = GCD (16, 4) = GCD (4, 0) = 4 implies that the GCD of 36 and 20 is 4. It can be shown that for any two starting numbers, this repeated reduction eventually produces a pair where the second number is 0. Then the GCD is the other number in the pair. Now, Write a method named gcd that computes the greatest common divisor of two.
Explanation / Answer
#include
void main()
{
int x,y,f1[100],f2[100],c[1000],i,j,k,l,m,n;
printf(" input the 2 numbers whose hcf is to be found ");
scanf("%d%d",&x,&y);
for(j=0,i=1;i<=x/2;i++)
{
if(x%i==0)
{
f1[j]=i;
j++;
}
}
f1[j]=x;
j++;
for(k=0,i=1;i<=y/2;i++)
{
if(y%i==0)
{
f2[k]=i;
k++;
}
}
f2[k]=y;
k++;
printf(" factors of first number ");
for(i=0;i<j;i++)
{ printf("%d ",f1[i]);
}
printf(" factors of second number ");
for(i=0;i<k;i++)
{ printf("%d ",f2[i]);
}
for(m=0,i=0;i<j;i++)
{
for(n=0;n<k;n++)
{
if(f1[i]==f2[n])
{
c[m]=f1[i];
m++;
}
}
}
printf(" Common factors ");
for(i=0;i<m;i++)
printf("%d ",c[i]);
printf(" GCD (Greatest Common Factor): %d ",c[i-1]);
printf(" LCM (Least Common Factor: ");
if(c[1]=='')
printf("%d",c[0]);
else
printf("%d",c[1]);
getch();
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.