php计算两个整数的最大公约数常用算法小结
作者:OSC首席键客 发布时间:2023-11-20 00:29:01
标签: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 <= $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程序设计有所帮助。
0
投稿
猜你喜欢
- 先来了解一下收/发邮件有哪些协议:SMTP协议 SMTP(Simple Mail Transfer Protocol),即简单邮件传输协议。
- 网页广告 Banner 设计图文手册:采用以下要点来改善你的BANNER。广告并不便宜。 确信你的广告被第一时间读到。使用像这样的Sans
- js实现千分符转化function fmoney(s, n){ n = n > 0 && n <= 20 ? n
- 【MySql常用命令】1:使用SHOW语句找出在服务器上当前存在什么数据库:mysql> SHOW DATABASES;2:创建一个数
- 代码如下:set fso=server.createobject("scripting.filesystemobject"
- Oracle 数据库启动Oracle shutdown的时候突然断电,导致使用sql/plus启动时无法连接到数据库,具体描述为: conn
- 网页过渡是指当浏览者进入或离开网页时,页面呈现的不同的刷新效果,比如卷动、百叶窗等。这样你的网页看起来
- 几个常用的js小函数,在表单验证时也许您用得到:一检查是否是email地址,二检查是否为数字,三检查是否为电话号码,四检查num是否是负数或
- 不用整天为美化select控件烦恼了。1、可批量美化select控件。2、可以有onchange句柄。3、触发onchange的函数可带参数
- <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN&
- 平时在PL/SQL中的编程中遇到一些问题,这里以问答的形式来进行把它们总结下来,以供大家分享。1、当需要向表中装载大量的数据流或者需要处理大
- 这是为了实现一个效果,而提前作的测试代码!看起来很简单的一个东西,到这会,大约四个小时过去了。不知道是IE6的BUG;还是我自已的BUG!有
- 在网页设计初期,我们会先收集大家对设计方向的期许,我们经常收集到这样的建议:产品经理:要易用,要简洁设计总监:要特色,要亮点部门经理:要大气
- 最近,Facebook设计团队在其位于加州帕罗奥多市(Palo Alto)的总部,提到了他们为2.5亿用户设计的原理和方法。 他们特别强调了
- 析构函数当某个对象成为垃圾或者当对象被显式销毁时执行。PHP5中提供的析构函数是__destruct,其与构造方法__construct相对
- 这几天在QQ群里知道了几个比较好的优化方面的站,感觉看高手的文章简直就是一种享受。和很多现在正在阅读这篇文章的站长一样,我即将毕业,但是还没
- 很多人说设计是力求细节的,在网页设计里表达出的细节就是图标。图标在一个设计里带来了额外的注解并且使设计里的对象和元素引起用户的注意。以下介绍
- 第一章:日志管理 1.forcing log switchessql> alter system switch logfile;2.f
- 非常好的一篇技术文档,翻译自Louis Lazaris 2009年9月15日发表的《The Z-Index CSS Property: A
- FlashPaper 是Macromedia推出的一款电子文档类工具,通过使用本程序,你可以将需要的文档通过简单的设置转换为SWF格式的Fl