How To Find The GCD Of Two Integers In PHP

Last updated: March 31, 2018 at 21:53 pm

I am writing this as a follow-up to a previous article I wrote on how to find the gcd of two integers in python here. The gcd of two integers is the largest integer that divides evenly into both integers with no remainder. This article describes how to make an html form, and then submit data to a php file which then calculates the gcd of the two integers.

Calculate The GCD OF Two Integers With User Input
Through The Browser.

Getting user input in PHP through forms is slightly cumbersome, but I will walk you though what you need to do. First, you need to create an HTML form.

A form is something that has things like boxes where you fill in data and where you submit data.

Below is the code for the form that I created to let a user submit 2 integers which then posts to a different php file that actually calculates the gcd.

<form action="calculate_gcd.php" method="post">Enter your first integer <input name="integer1" type="text" />
 Enter your second integer <input name="integer2" type="text" />
 <input name="submit" type="submit" value="Calculate!" />

calculate_gcd.php is the name of the file that this form will submit the user’s input data to.

You can download the code for this form as a text file here. Be sure to then rename it as a .html or .php file.

Test The GCD HTML Form

Here, you can test the form on my server where you can submit 2 different integers to calculate their gcd. You can reload this form to redo the calculation.

Calculating The GCD From User Input Through The Browser

So far we have only created a form, but that just submits data. We haven’t calculated anything yet.

Now for the code that actually calculates the gcd.


#Created Dec 18 02:09:31 2016
#author: Justin, owner of
$first_integer = $_POST['integer1'];
$second_integer= $_POST['integer2'];

function gcd($x, $y)
    /*This function finds the gcd (greatest common divisor)
    of the two integers $x and $y and returns the gcd
    It uses the Euclidean Algorithm.
    The general form for the Euclidean Algorithm is
    r_k = q_(k+2)*r_(k+1) + r_(k+2)
    Here _ denotes subscripts. 
    Above Parentheses indicate that the subscript is more than 1 character long
    for the code I just remove the _ and ()
    initially $r_k = $x and $r_(k+1) = $y
    if ($x == $y)
        return $x;
    elseif ($x == 0 or $y == 0)
        return 1;
        #we assume $x is greater than y. If $y is greater than $x, 
        #just switch them
        if ($y > $x)
            $temp = $x;
            $x = $y;
            $y = $temp;
        $rk = $x;
        $rkp1 = $y;
        $rkp2 = $rk % $rkp1;
        if ($rkp2 == 0)
            return $rkp1;
            while ($rkp2 != 0)
                $rk = $rkp1;
                $rkp1 = $rkp2;
                $rkp2 = $rk % $rkp1;
            return $rkp1;

$result = gcd($first_integer, $second_integer);
echo "the gcd of $first_integer and $second_integer is $result";

You can download this php code that calculates the gcd of two numbers after data is submitted through the file form_for_gcd.php here. Make sure that you rename the .txt file as a .php file.

Once again, you can test my form here, which will calculate the gcd of 2 integers. The important thing is that you actually put it onto your own server so that you know you can run it. You first run the form, and then you should see output on calculate_gcd.php

Final Notes

Make sure that you put the two files calculate_gcd.php and form_for_gcd.php in the same folder on your server.

In addition, make sure that you have a web server like Apache installed, php mod for your server installed, and PHP itself installed on your server. Currently, PHP is in version 7.0. If you use a shared web host, it is very likely your host has already installed and configured PHP, so you probably don’t have to worry about it. You will only need to make sure it is installed if you run your own server or use a VPS.

What did you think of this article? Did you learn anything useful about PHP? Let’s discuss it in the comments below.

2 thoughts on “How To Find The GCD Of Two Integers In PHP”

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.