php计算两个整数的最大公约数常用算法小结
作者:OSC首席键客 时间:2023-11-20 00:29:01
本文实例讲述了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 <= $num; $i++) {
$a[$i] = $i;
}
for( $i = 2; $i <= floor( sqrt($num) ); $i++ ) {
if($a[$i] != 0) {
$j = $i * $i;
while($j <= $num) {
$a[$j] = 0;
$j = $j + $i;
}
}
}
$p = 0;
for($i = 2; $i <= $num; $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 '<br>' . sprintf('%1.10f', $time) . 'seconds';
希望本文所述对大家的php程序设计有所帮助。
标签:php,计算,公约数,算法
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
Python实现打乒乓小游戏
2023-07-20 04:48:53
![](https://img.aspxhome.com/file/2023/1/105391_0s.gif)
ProC 连接Oracle代码
2009-06-10 18:12:00
Python 正则表达式入门(初级篇)
2021-12-03 23:41:12
python+playwright微软自动化工具的使用
2022-10-18 08:52:29
![](https://img.aspxhome.com/file/2023/1/112531_0s.png)
Python实现模拟登录及表单提交的方法
2021-05-28 19:23:12
Python socket实现多对多全双工通信的方法
2023-05-02 17:31:38
在微信小程序里使用watch和computed的方法
2024-04-10 16:16:40
Python使用POP3和SMTP协议收发邮件的示例代码
2023-10-03 15:37:28
![](https://img.aspxhome.com/file/2023/0/62890_0s.jpg)
BootStrap modal实现拖拽功能
2024-04-18 09:43:48
np.random.seed() 的使用详解
2021-04-08 23:54:57
![](https://img.aspxhome.com/file/2023/0/117430_0s.png)
使用php-timeit估计php函数的执行时间
2023-10-07 19:56:50
原生JS与jQuery编写简单选项卡
2024-04-30 09:52:52
innodb_flush_method取值方法(实例讲解)
2024-01-13 10:12:44
CentOS7下mysql 8.0.16 安装配置方法图文教程
2024-01-22 11:49:56
![](https://img.aspxhome.com/file/2023/3/66143_0s.png)
python安装sklearn模块的方法详解
2023-08-01 17:23:48
![](https://img.aspxhome.com/file/2023/9/61969_0s.jpg)
Windows下用py2exe将Python程序打包成exe程序的教程
2021-07-11 23:03:17
使用Pyinstaller转换.py文件为.exe可执行程序过程详解
2022-11-30 22:43:40
![](https://img.aspxhome.com/file/2023/8/79728_0s.png)
pytorch-神经网络拟合曲线实例
2022-03-17 18:17:30
![](https://img.aspxhome.com/file/2023/5/66815_0s.jpg)
Python之修改图片像素值的方法
2022-03-14 03:46:18
Python实现RGB等图片的图像插值算法
2023-03-30 17:11:55
![](https://img.aspxhome.com/file/2023/9/67279_0s.jpg)