Math

Euclidean Algorithm, Erotosthenes Sieve
Type:	application
Added by:	vsramamurthi
Entered:	18/11/2000
Last modified:	01/12/2000
Rating:	- (fewer than 3 votes)
Views:	6400
An application for doing exact integer computations. Uses bcmath functions of PHP. The Euclidean Algorithm and the Sieve of Erotesthenes are implemented.
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">

                            <HTML>

                            <HEAD><TITLE>Number Theory Assistant</TITLE></HEAD>

                            <BODY BGCOLOR="#336699" TEXT="FFFFFF" LINK="0000FF" VLINK="800080" ALINK="FF0000">

                            <CENTER>

                            <TABLE BORDER="1"><TR><TD><FONT SIZE=+3><CENTER>Number Theory Assistant</FONT><BR>&copy Dr. Rama Rao</CENTER><P>


                            <FONT SIZE=+1>TYPE THE NUMBERS AND CHOOSE AN OPERATION</FONT><P>

                            <form action="/php/numth.php3" method="GET">

                                    <input type="text" name="m">: = m<br>

                                    <input type="text" name="n">: = n<br>

                                <input type="text" name="p">: = p<p>

                            <FONT SIZE=+1>Choose an operation</FONT><P>

                                    <select multiple name="choice" size="9">

                                      <option value="no1">m + n

                                        <option value="no2">m * n

                                        <option value="no3">quo(m / n)

                                      <option value="no4">m mod n

                                      <option value="no5">m ^ n

                                      <option value="no6">m ^ n mod p

                                    <option value="no7">gcd(m, n)

                                    <option value="no8">gcd = m*x + n*y

                                    <option value="no9">primes <= m

                                  </select>

                                    <input type="submit" value="Compute">

                            </form>

                            

                            </TD>

                            <TD width="40%" VALIGN="TOP">

                            

                            <FONT SIZE=+2>RESULTS</FONT><P>

                            <?

                            
 if ($choice == "no1") {echo bcadd($m,$n)."=  m + n<br>";}

                            if ($choice == "no2") {echo bcmul($m,$n)."=  m * n<br>";}

                            if ($choice == "no3") {echo bcdiv($m,$n)."=  quo(m / n)<br>";}

                            if ($choice == "no4") {echo bcmod($m,$n)."=  m mod n<br>";}

                            if ($choice == "no5") {echo bcpow($m,$n)."=  m ^ n<br>";}

                            if ($choice == "no6") {echo bcmod(bcpow($m,$n),$p)."=  m ^ n mod p<br>";}

                            

                            if ($choice == "no7") {

                            if ($m > $n): 
 $a = $m; $b = $n; 

                            else: 
 $a = $n; $b = $m; 

                            endif;

                            do {
 $r = bcmod($a,$b); $q = bcdiv($a,$b);echo "$a=$q*$b+$r<br>"; $a = $b; $b = $r;

                            }

                            while ($r!= 0);

                            echo "gcd of $m and $n is $a";

                            }

                            

                            if ($choice == "no8") {

                            if ($m > $n): 
 $a = $m; $b = $n; 

                            else: 
 $a = $n; $b = $m; 

                            endif;
 $ini1=array($a,1,0); $ini2=array($b,0,1);
 $x=$ini1; $y=$ini2;

                            do {
 $r=bcmod($x[0],$y[0]); $q=bcdiv($x[0],$y[0]);
 $temp=$y; $y=array($r,$x[1]-bcmul($q,$y[1]),$x[2]-bcmul($q,$y[2]));$x=$temp;

                            } while ($r!=0);

                            echo "gcd($m,$n) = $x[0]"; echo "<BR>";

                            echo "$x[0] = ($x[1]) * $ini1[0] + ($x[2]) * $ini2[0]";

                            }

                            

                            if ($choice == "no9") {
 $c=", ";
 $prime=array(2,3);
 $i=4;

                            do {
 $rem=1;

                            for ($j=0; $j<count($prime); $j++) {
 $rem=$rem*bcmod($i, $prime[$j]);

                            }

                            if ($rem != 0) {$prime[]=$i;}
 //only PHP4->{array_push($prime, $i);}
 $i++;

                            } 

                            while ($i <= $m);

                            function disp($entry) {echo $entry.", ";}
 array_walk($prime, 'disp');

                            

                            print "<BR>There are ".count($prime)." primes.";

                            }

                            
 ?>


                            

                            </TD></TR></TABLE>

                            </CENTER>

                            </BODY></HTML>
Usage Example
Rate This Script
Zend - The PHP Company

Math

Search
