Inhaltsverzeichnis
php计算两个整数的最大公约数常用算法小结
Heim Backend-Entwicklung PHP-Tutorial php计算两个整数的最大公约数常用算法小结_PHP教程

php计算两个整数的最大公约数常用算法小结_PHP教程

Jul 13, 2016 am 10:05 AM
php 常用 整数 最大公约数 von 算法 计算

php计算两个整数的最大公约数常用算法小结

 这篇文章主要介绍了php计算两个整数的最大公约数常用算法,实例总结了求最大公约数的三种常用方法,具有一定参考借鉴价值,需要的朋友可以参考下

 

 

本文实例讲述了php计算两个整数的最大公约数常用算法。分享给大家供大家参考。具体如下:

 

代码如下:

//计时,返回秒
function microtime_float ()
{
list( $usec , $sec ) = explode ( " " , microtime ());
return ((float) $usec + (float) $sec );
}
//////////////////////////////////////////
//欧几里得算法
function ojld($m, $n) {
if($m ==0 && $n == 0) {
return false;
}
if($n == 0) {
return $m;
}
while($n != 0){
$r = $m % $n;
$m = $n;
$n = $r;
}
return $m;
}
//////////////////////////////////////////
//基于最大公约数的定义
function baseDefine($m, $n) {
if($m ==0 && $n == 0) {
return false;
}
$min = min($m, $n);
while($min >= 1) {
if($m % $min == 0){
if($n % $min ==0) {
return $min;
}
}
$min -= 1;
}
return $min;
}
////////////////////////////////////////////
//中学数学里面的计算方法
function baseSchool($m, $n) {
$mp = getList($m); //小于$m的全部质数
$np = getList($n); //小于$n的全部质数
$mz = array(); //保存$m的质因数
$nz = array(); //保存$n的质因数
$mt = $m;
$nt = $n;
//m所有质因数
//遍历m的全部质数,当能够被m整除时,继续下一次整除,知道不能被整除再取下一个能够被m整除
//的质数,一直到所有出现的质数的乘积等于m时停止
foreach($mp as $v) {
while($mt % $v == 0) {
$mz[] = $v;
$mt = $mt / $v;
}
$c = 1;
foreach($mz as $v) {
$c *= $v;
if($c == $m){
break 2;
}
}
}
//n所有质因数
foreach($np as $v) {
while($nt % $v == 0) {
$nz[] = $v;
$nt = $nt / $v;
}
$c = 1;
foreach($nz as $v) {
$c *= $v;
if($c == $n){
break 2;
}
}
}
//公因数
$jj = array_intersect($mz, $nz); //取交集
$gys = array();
//取出在俩数中出现次数最少的因数,去除多余的。
$c = 1; //记录数字出现的次数
$p = 0; //记录上一次出现的数字
sort($jj);
foreach($jj as $key => $v) {
if($v == $p) {
$c++;
}
elseif($p != 0) {
$c = 1;
}
$p = $v;
$mk = array_keys($mz, $v);
$nk = array_keys($nz, $v);
$k = ( count($mk) > count($nk) ) ? count($nk) : count($mk);
if($c > $k) {
unset($jj[$key]);
}
}
$count = 1;
foreach($jj as $value) {
$count *= $value;
}
return $count;
}
//求给定大于等于2的整数的连续质数序列
//埃拉托色尼筛选法
function getList($num) {
$a = array();
$a = array();
for($i = 2; $i $a[$i] = $i;
}
for( $i = 2; $i if($a[$i] != 0) {
$j = $i * $i;
while($j $a[$j] = 0;
$j = $j + $i;
}
}
}
$p = 0;
for($i = 2; $i if($a[$i] != 0) {
$L[$p] = $a[$i];
$p++;
}
}
return $L;
}
/////////////////////////////////////
//test
$time_start = microtime_float ();
//echo ojld(60, 24); //0.0000450611 seconds
//echo baseDefine(60, 24); //0.0000557899 seconds
echo baseSchool(60, 24); //0.0003471375 seconds
$time_end = microtime_float ();
$time = $time_end - $time_start ;
echo '
' . sprintf('%1.10f', $time) . 'seconds';

 

希望本文所述对大家的php程序设计有所帮助。

www.bkjia.comtruehttp://www.bkjia.com/PHPjc/963981.htmlTechArticlephp计算两个整数的最大公约数常用算法小结 这篇文章主要介绍了php计算两个整数的最大公约数常用算法,实例总结了求最大公约数的三种常...
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn

Heiße Artikel -Tags

Notepad++7.3.1

Notepad++7.3.1

Einfach zu bedienender und kostenloser Code-Editor

SublimeText3 chinesische Version

SublimeText3 chinesische Version

Chinesische Version, sehr einfach zu bedienen

Senden Sie Studio 13.0.1

Senden Sie Studio 13.0.1

Leistungsstarke integrierte PHP-Entwicklungsumgebung

Dreamweaver CS6

Dreamweaver CS6

Visuelle Webentwicklungstools

SublimeText3 Mac-Version

SublimeText3 Mac-Version

Codebearbeitungssoftware auf Gottesniveau (SublimeText3)

PHP 8.4 Installations- und Upgrade-Anleitung für Ubuntu und Debian PHP 8.4 Installations- und Upgrade-Anleitung für Ubuntu und Debian Dec 24, 2024 pm 04:42 PM

PHP 8.4 Installations- und Upgrade-Anleitung für Ubuntu und Debian

CakePHP Datum und Uhrzeit CakePHP Datum und Uhrzeit Sep 10, 2024 pm 05:27 PM

CakePHP Datum und Uhrzeit

CakePHP-Projektkonfiguration CakePHP-Projektkonfiguration Sep 10, 2024 pm 05:25 PM

CakePHP-Projektkonfiguration

CakePHP-Datei hochladen CakePHP-Datei hochladen Sep 10, 2024 pm 05:27 PM

CakePHP-Datei hochladen

CakePHP-Routing CakePHP-Routing Sep 10, 2024 pm 05:25 PM

CakePHP-Routing

Besprechen Sie CakePHP Besprechen Sie CakePHP Sep 10, 2024 pm 05:28 PM

Besprechen Sie CakePHP

So richten Sie Visual Studio-Code (VS-Code) für die PHP-Entwicklung ein So richten Sie Visual Studio-Code (VS-Code) für die PHP-Entwicklung ein Dec 20, 2024 am 11:31 AM

So richten Sie Visual Studio-Code (VS-Code) für die PHP-Entwicklung ein

CakePHP-Kurzanleitung CakePHP-Kurzanleitung Sep 10, 2024 pm 05:27 PM

CakePHP-Kurzanleitung

See all articles