'C# find the greatest common divisor
"The greatest common divisor of two integers is the largest integer that evenly divides each of the two numbers. Write method Gcd that returns the greatest common divisor of two integers. Incorporate the method into an app that reads two values from the user and displays the result."
(this is not homework, just an exercise in the book I'm using)
can you help me solve this? Here's what I've got so far.
(edit - I can submit the two numbers but it won't calculate the Gcd for me)
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Greatest_Common_Divisor
{
class Program
{
static int GetNum(string text)
{
bool IsItANumber = false;
int x = 0;
Console.WriteLine(text);
do
{
IsItANumber = int.TryParse(Console.ReadLine(), out x);
} while (!IsItANumber);
return x;
}
static void Main(string[] args)
{
string text = "enter a number";
int x = GetNum(text);
text = "enter a second number";
int y = GetNum(text);
int z = GCD(x, y);
Console.WriteLine(z);
}
private static int GCD(int x, int y)
{
int v = 0;
int n = 0;
v = GetGreatestDivisor(x, y);
return v;
}
static int GetGreatestDivisor(int m, int h)
{
do
{
for (int i = m; i <= 1; i--)
if (m%i == 0 && h%i == 0)
{
int x = 0;
x = i;
return x;
}
} while (true);
return m;
}
}
}
Solution 1:[1]
Here's an implementation of the Euclidean algorithm that returns the greatest common divisor without performing any heap allocation.
You can substitute ulong for uint if needed. An unsigned type is used, as the technique does not work for signed values. If you know your a and b values are not negative, you can use long or int instead.
private static ulong GCD(ulong a, ulong b)
{
while (a != 0 && b != 0)
{
if (a > b)
a %= b;
else
b %= a;
}
return a | b;
}
This method is used in my metadata-extractor library, where it has associated unit tests.
Solution 2:[2]
Using LINQ's Aggregate method:
static int GCD(int[] numbers)
{
return numbers.Aggregate(GCD);
}
static int GCD(int a, int b)
{
return b == 0 ? a : GCD(b, a % b);
}
Note: answer above borrowed from accepted answer to Greatest Common Divisor from a set of more than 2 integers.
Solution 3:[3]
You can try using this:
static int GreatestCommonDivisor(int[] numbers)
{
return numbers.Aggregate(GCD);
}
static int GreatestCommonDivisor(int x, int y)
{
return y == 0 ? x : GreatestCommonDivisor(y, x % y);
}
Solution 4:[4]
Try this:
public static int GCD(int p, int q)
{
if(q == 0)
{
return p;
}
int r = p % q;
return GCD(q, r);
}
Solution 5:[5]
public class GCD
{
public int generalizedGCD(int num, int[] arr)
{
int gcd = arr[0];
for (int i = 1; i < num; i++) {
gcd = getGcd(arr[i], gcd);
}
return gcd;
}
public int getGcd(int x, int y)
{
if (x == 0)
return y;
return getGcd(y % x, x);
}
}
Solution 6:[6]
By using this, you can pass multiple values as well in the form of array:-
// pass all the values in array and call findGCD function
int findGCD(int arr[], int n)
{
int gcd = arr[0];
for (int i = 1; i < n; i++) {
gcd = getGcd(arr[i], gcd);
}
return gcd;
}
// check for gcd
int getGcd(int x, int y)
{
if (x == 0)
return y;
return gcd(y % x, x);
}
Solution 7:[7]
List<int> gcd = new List<int>();
int n1, n2;
bool com = false;
Console.WriteLine("Enter first number: ");
n1 = int.Parse(Console.ReadLine());
Console.WriteLine("Enter second number: ");
n2 = int.Parse(Console.ReadLine());
for(int i = 1; i <= n1; i++)
{
if(n1 % i == 0 && n2% i == 0)
{
gcd.Add(i);
}
if(i == n1)
{
com = true;
}
}
if(com == true)
{
Console.WriteLine("GCD of {0} and {1} is {2}.", n1, n2, gcd[gcd.Count - 1]);
}
Console.ReadLine();
Solution 8:[8]
If efficiency is not a big concern this will do the job.
// gets greatest common divisor of A and B.
var GCD=Enumerable.Range(1,Math.Min(A,B)).Last(n=>(A%n | B%n)==0);
Solution 9:[9]
int[] nums = new int[] {6,12,24,48};
int GCD(int a, int b) => b == 0 ? a : GCD(b, a % b);
int FindGCD(int[] numbers) => numbers.Aggregate(GCD);
Console.WriteLine($"List of numbers ({String.Join(',',nums)})");
Console.WriteLine($"Smallest number: {nums.Min()}");
Console.WriteLine($"Largest number: {nums.Max()}");
Console.WriteLine($"Greatest common devisor of {nums.Min()} and {nums.Max()}: {GCD(nums.Min(),nums.Max())}");
Console.WriteLine($"Aggregate common devisor of array ({String.Join(',',nums)}): {FindGCD(nums)}");
List of numbers (6,12,24,48)
Smallest number: 6
Largest number: 48
Greatest common devisor of 6 and 48: 6
Aggregate common devisor of array (6,12,24,48): 6
Solution 10:[10]
Here is a simple solution.
You can use BigInteger to get the greatest common divisor. Just do not forget to add using System.Numerics; to the top of your code.
using System.Numerics;
public class Program{
public static void Main(String[] args){
int n1 = 1;
int n2 = 2;
BigInteger gcd = BigInteger.GreatestCommonDivisor(n1,n2);
Console.WriteLine(gcd);
}
}
Solution 11:[11]
using System;
//Write a function that returns the greatest common divisor (GCD) of two integers
namespace GCD_of_Two_Numbers
{
class Program
{
public static void Gcd(int num1, int num2)
{
int[] temp1 = new int[num1];
int[] temp2 = new int[num2];
int[] common = new int[10];
for(int i=2;i<num1/2;i++)
{
if(num1 % i ==0)
{
temp1[i] = i;
}
}
for (int i = 2; i < num2/2; i++)
{
if (num2 % i == 0)
{
temp2[i] = i;
}
}
int len = temp1.Length + temp2.Length;
for(int i=0;i<len;i++)
{
if(temp1[i]==temp2[i])
{
common[i] = temp1[i];
}
}
int max_number = common[0];
for(int i=0;i<common.Length;i++)
{
if(max_number < common[i])
{
max_number = common[i];
}
}
Console.WriteLine($"The Greatest Common Diviser is {max_number}");
}
static void Main(string[] args)
{
Gcd(32, 8);
}
}
}
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow