Official Everybody Edits Forums

realmaster42

Formerly marcoantonimsantos

From: ̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍

Joined: 2015-02-20

Posts: 1,380

Website

Greatest Comum Divisor

So i found a way to find the Greatest Comum Divisor between two numbers, and it's tested.

If you don't know what GCD is, then or search math OR:

GCD is the highest integer between two number's divisors that matches.

It was coded in LUA just today

▼Hidden LUA

MathToolsKey.GetDivisors = function(number)
	if (tonumber(number)~=nil) then
		local Divisores = {}
		
		for i=1,number do
			if number/i == math.floor(number/i) then
				table.insert(Divisores, number/i)
			end
		end
		
		return Divisores
	else
		return {1}
	end
end

MathToolsKey.GCD = function(number, num) -- Greatest Comum Divisor
	if (tonumber(number)~=nil) then
		if (tonumber(num)~=nil) then
			local Div1 = MathToolsKey.GetDivisors(number)
			local Div2 = MathToolsKey.GetDivisors(num)
			
			local oneBet = 1
			local twoBet = 1
			
			for i=1,#Div1 do
				if Div1[i] > twoBet then
					for i=1,#Div2 do
				    if Div2[i] > oneBet then
			  		twoBet = Div2[i]
			    	end
			        end
					oneBet = Div1[i]
				end
			end
			if twoBet>oneBet then
				twoBet = oneBet
			elseif oneBet>twoBet then
				oneBet = twoBet
			end
			
			return oneBet
		else
			return 1
		end
	else
		return 1
	end
end

C#:

▼READ ME

public List<int> GetDivisors(int number){
		List<int> Divisores = new List<int>(){}
		
		for (int i=1;i<number;i++) {
			if (number/i == math.floor(number/i)){ //pls someone make math.floor something right 
				Divisores.Add(number/i)
			}
		}
		
		return Divisores
}

public int GCD(int number, int num){ // Greatest Comum Divisor
			List<int> Div1 = GetDivisors(number)
			List<int> Div2 = GetDivisors(num)
			
			int oneBet = 1
			int twoBet = 1
			
			for (int i=1;i<Div1.Count;i++) do
				if (Div1[i] > twoBet){
			            for (int i=1;i<Div2.Count;i++) {
				    if (Div2[i] > oneBet){
			  		twoBet = Div2[i]
			    	    }}
			        }
					oneBet = Div1[i]
			end
			if (twoBet>oneBet)
				twoBet = oneBet
			else if (oneBet>twoBet){
				oneBet = twoBet}
			
			return oneBet
}

---

SmittyW

Member

Joined: 2015-03-13

Posts: 2,085

Re: Greatest Comum Divisor

MCD, also known as GCD (Greatest Common Divisor) for you fellow english folks. This honestly got me confused for a second before I realized you were spanish. Anyway, I guess it's nice to know they have it. Is it really ground-breaking news?

realmaster42

Formerly marcoantonimsantos

From: ̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍

Joined: 2015-02-20

Posts: 1,380

Website

Re: Greatest Comum Divisor

MCD, also known as GCD (Greatest Common Divisor) for you fellow english folks. This honestly got me confused for a second before I realized you were spanish. Anyway, I guess it's nice to know they have it. Is it really ground-breaking news?

wtfno why does everyone think im spanish

You nuggets it's MARCO NOT MARCOS

ANTONIO NOT ANTONIOS

I'm PT

anyways okay. here its MDC

---

TiKen

Member

Joined: 2015-02-24

Posts: 298

Re: Greatest Comum Divisor

Off-topic: Marco and Antonio are also Italian names. Are you Italian?

On-topic: Better solutions where found with the GOOGLE research "greater common factor c#". It's only the 3rd link. It took me 30sec.

realmaster42

Formerly marcoantonimsantos

From: ̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍

Joined: 2015-02-20

Posts: 1,380

Website

Re: Greatest Comum Divisor

Off-topic: Marco and Antonio are also Italian names. Are you Italian?

On-topic: Better solutions where found with the GOOGLE research "greater common factor c#". It's only the 3rd link. It took me 30sec.

Off-topic: I've said im portuguese. now plsgo.

On-topic: Who cares, I'm showing a new way of reaching there. Can you actually read why Bots and 'Programming' ('Programming') word exists?

---

Xfrogman43

Member

From: need to find a new home

Joined: 2015-02-15

Posts: 4,174

Re: Greatest Comum Divisor

Basically you wanted to create something new and you did it? Well congratulations on your success.
Note: Haters everywhere and people who would rather use google or something else to find answers rather than coming up with it on their own.

---

thanks zoey aaaaaaaaaaaand thanks latif for the avatar

TiKen

Member

Joined: 2015-02-24

Posts: 298

Re: Greatest Comum Divisor

Ok different points:

• Yes, "Bots and programming" contains indeed "Programming" (and yes this word exists). However, the problem and solution you show here are (apart from the fact that you gave c# code) not exactly related to EE, but more to general programming.
  Do you see me creating topics here about this N-D parametric active contours method I coded recently? (hint: the answer starts with 'n' and finishes with 'o')

• And yes, you're super happy because you created a cool code that is very inefficient.
  Your algorithm has at least a O(n) complexity, which is (sure), not too bad. However, the Euclidean algorithm (the one used in the link I found) that I learn in middle school (and forgot about) has a way better complexity (O(#of digits²)).

  The guy (Euclide) who invented this simple, yet effective algorithm lived in 300 BC.

  Do we have to re-invent the wheel every time we create a car? Again, the answer is no. (hopefully, otherwise we would still be fighting each others with sticks n' stones)

I'm a bit sorry it falls on you, but it just gets very annoying: most of the topic on the "Bots and Programming" forum are now wannabe "bot-makers" that do not know how to proofread a code for a missing semicolon or how to use Google to find answers they'll get way faster than posting here.

There is no shame in asking for help, but is it necessary to post it here? Is it really related to EE? Or is it just a general problem? Same goes for the "tips" that people found interesting.

This section seems to be stagnating into the primordial soup of development... T_T

Finally: Now, I don't ask people to simply copy-paste what they found on the net. Most of the time it won't work. You have to read the stuff, understand it, and then rewrite it on your own.

P.S.: Hater? No. I just try to learn from others and there's no shame in that.
P.P.S.: Off-topic was a joke. Humor? Get it?

realmaster42

Formerly marcoantonimsantos

From: ̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍

Joined: 2015-02-20

Posts: 1,380

Website

Re: Greatest Comum Divisor

Ok different points:

• Yes, "Bots and programming" contains indeed "Programming" (and yes this word exists). However, the problem and solution you show here are (apart from the fact that you gave c# code) not exactly related to EE, but more to general programming.
  Do you see me creating topics here about this N-D parametric active contours method I coded recently? (hint: the answer starts with 'n' and finishes with 'o')

• And yes, you're super happy because you created a cool code that is very inefficient.
  Your algorithm has at least a O(n) complexity, which is (sure), not too bad. However, the Euclidean algorithm (the one used in the link I found) that I learn in middle school (and forgot about) has a way better complexity (O(#of digits²)).

  The guy (Euclide) who invented this simple, yet effective algorithm lived in 300 BC.

  Do we have to re-invent the wheel every time we create a car? Again, the answer is no. (hopefully, otherwise we would still be fighting each others with sticks n' stones)

I'm a bit sorry it falls on you, but it just gets very annoying: most of the topic on the "Bots and Programming" forum are now wannabe "bot-makers" that do not know how to proofread a code for a missing semicolon or how to use Google to find answers they'll get way faster than posting here.

There is no shame in asking for help, but is it necessary to post it here? Is it really related to EE? Or is it just a general problem? Same goes for the "tips" that people found interesting.

This section seems to be stagnating into the primordial soup of development... T_T

Finally: Now, I don't ask people to simply copy-paste what they found on the net. Most of the time it won't work. You have to read the stuff, understand it, and then rewrite it on your own.

P.S.: Hater? No. I just try to learn from others and there's no shame in that.
P.P.S.: Off-topic was a joke. Humor? Get it?

I am a bot maker but i do not post everything i don't know here. Please...

Also okay.
(I made this from the scratch, plsgo)

---

Zumza

Member

From: root

Joined: 2015-02-17

Posts: 4,656

Re: Greatest Comum Divisor

How it should be done in my opinion:

int gcd(int a, int b) {

     while(a != b)
          if(a < b)
               b-= a;
          else
               a-= b;
      return a;

}

---

Everybody edits, but some edit more than others

goeyfun

Member

From: Mighty Japan

Joined: 2015-02-18

Posts: 667

Re: Greatest Comum Divisor

plz no
Wasting memory and long run-time
try using Euclidean algorithm

scanf("%d %d",&a,&b);
while(b>0){
int temp=a%b; 
a=b; 
b=tmp;
}
GCD=A;

---

Zumza

Member

From: root

Joined: 2015-02-17

Posts: 4,656

Re: Greatest Comum Divisor

The operation of subtraction is faster than division, particularly for large numbers

The efficient algorithm is the one who suits the input best...

Edit: Binary GCD algorithm should also be noticed.

---

Everybody edits, but some edit more than others

ewoke

Member

Joined: 2015-02-20

Posts: 412

Re: Greatest Comum Divisor

private static int gcd(int a, int b) 
{
	int t;
 
	// Ensure B > A
	if (a > b) 
	{
		t = b;
		b = a;
		a = t;
	}
 
	// Find 
	while (b != 0)
	{
		t = a % b;
		a = b;
		b = t;
	}
 
	return a;
}

gotta love google

---

if you can read this....good for you

kurtv13

Member

From: Everywhere

Joined: 2015-04-24

Posts: 59

Re: Greatest Comum Divisor

The question is, why does this thread even exist?

---

SmittyW

Member

Joined: 2015-03-13

Posts: 2,085

Re: Greatest Comum Divisor

The question is, why does this thread even exist?

Do you want to start a flame war? Because this is how you start a flame war.

Marco just wanted to show his work, so then people offer their criticism to make it better, even if there is a better one on google. This is how this thread works.

@marco
Sorry I got your nationality mixed up, I didn't mean anything by it. I just googled MCD and it turned up spanish.

realmaster42

Formerly marcoantonimsantos

From: ̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍̍

Joined: 2015-02-20

Posts: 1,380

Website

Re: Greatest Comum Divisor

The question is, why does this thread even exist?

The question is, why does this thread even exist?

Do you want to start a flame war? Because this is how you start a flame war.

Marco just wanted to show his work, so then people offer their criticism to make it better, even if there is a better one on google. This is how this thread works.

@marco
Sorry I got your nationality mixed up, I didn't mean anything by it. I just googled MCD and it turned up spanish.

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Well guys the advantage of this method is that you actually can check divisores.

---