# Greatest Common Factor Script

Discussion in 'Tutorials' started by JFitch, Apr 23, 2017.

1. ### JFitchMember

Joined:
Sep 28, 2016
Posts:
428
GM Version: GM Studio 1.4
Target Platform: ALL

Summary:
This tutorial gives a script for calculating the Greatest Common Factor of two numbers.

Tutorial:

The simplest way to calculate the greatest common factor of two numbers is to replace the larger number with the remainder when it's divided by the smaller number, and continue to do that until there's no remainder. With this script, you can just use gcf(a,b) to get the greatest common factor of a and b.
Code:
```var a=abs(argument);
var b=abs(argument);
var new_a;
var new_b;

while (a!=b && a!=0 && b!=0)
{
new_a=a mod b;
new_b=b mod a;
a=new_a;
b=new_b;
}

return max(a,b);```
If you want the greatest common factor of more than two numbers, first find the GCF of the first two numbers, then find the GCF of the result and the third number, then find the GCF of the result and the fourth number, etc. It would look like gcf(gcf(gcf(a,b),c),d).

Last edited by a moderator: Apr 23, 2017
2. ### chancepredictably randomForum StaffModerator

Joined:
Apr 22, 2016
Posts:
798
I haven't tested your algorithm carefully. I'll leave that to other members. But it looks interesting.

I'm interested in prime factorization and number theory. So I'm curious to see what other members have to say about your approach, and this area in general.

Last edited: Apr 23, 2017
3. ### JFitchMember

Joined:
Sep 28, 2016
Posts:
428
I actually added to it since posting it. The original post works for two numbers. I changed it to work for any amount of numbers.
Code:
```var a=argument;
var b;
var new_a;
var new_b;
var i;

for (i=1;i<argument_count;i++)
{
b=argument[i];

while (a!=b && a!=0 && b!=0)
{
new_a=a mod b;
new_b=b mod a;
a=new_a;
b=new_b;
}
a=max(a,b);
}
return a;```
With this code, instead of using the code gcf(gcf(gcf(a,b),c),d), you can use gcf(a,b,c,d).

4. ### AppsurdMember

Joined:
Jun 20, 2016
Posts:
238
Interesting script, it's simple and neat. But I once found another script online so I was interested to see whether both scripts were just as quick.

Code:
```// gcd(a,b)
// constraint: a>0 and b>0
var a,b;
a = argument0;
b = argument1;
while true {
a = a mod b;
if a=0 then return b;
b = b mod a;
if b=0 then return a;
}

```
Nothing special but a little different. I just this testing script.

Code:
```
N = 100000;

t1 = current_time;

for(i=0; i<N; i+=1)
{
var res = gcd(7583,59375);
}

t2 = current_time - t1;

for(i=0; i<N; i+=1)
{
var res = gcf(7583,59375);
}

t3 = current_time - t2;

show_message_async("The gcd script: Time: "+string(t2)+"#The gcf script: Time: "+string(t3));
```
And it turned out that your script is about two times slower than this old script I found (and no, it's not my script, just took it from the internet)

--------------

Another remark, perhaps you could look into Euclides's algorithm? It yields the gcf/gcd but also the numbers x and y such that
x a + y b = ggd(a,b)