len;
if($l < count($prims)) self::$inst->ints = $prims; // lista initiala de primi
else
{
$l = count($prims);
$v = self::$inst->reset;
for($i=0; $i<$l; $i++) if($v <> $prims[$i]) // daca in lista interna vreun nr e gresit
{
self::$inst->ints = $prims; // resetam lista
break;
}
else $v = self::$inst->next;
}
debug_('Prims->length: ' . self::$inst->len, __FILE__, __LINE__, "Prims::__construct");
}
else return false;
}
static function getInst()
{
if(empty(self::$inst)) new self();
return self::$inst;
}
/*------------------------------------------------------------------------------------------*/
/*! Nr elementelor prime din lista interna */
static function count() { return self::getInst()->len; }
/*! Lista interna de nr prime.
* Daca lista e mai mica ca $nr, se adauga nr neajuns la lista. */
static function lista($nr = 0)
{
$ps = &self::getInst();
if(!$nr) $nr = 4;
$nr -= $ps->len;
if($nr > 0) self::last($nr);
return $ps->ints;
}
/*! Sterge lista interna de primi, rezervand $preserv elemente. */
static function clear($preserv = 0)
{
$o = self::getInst();
return $o->len = $preserv;
}
/*!
* Returneaza ultimul prim din lista interna.
* Daca $nr > 0, adauga $nr primi la lista.
*
* Nota: Pentru valori mari ale $nr, dureaza mult...
* O($nr) = ($nr-$p)^2 (complexitatea)
*/
static protected function last($nr = 1)
{
// if($nr < 0) return false;
$o = self::getInst();
$p = $o->last;
while($nr)
{
$p += 2;
$sp = floor(sqrt($p));
$pr = true;
$d = $o->reset; // $d parcurge lista de nr prime - divizor
while($d !== false)
{
if($p % $d == 0){ $pr = false; break; } else
if($d >= $sp) break;
$d = $o->next;
}
if($pr)
{
$o->push($p);
$nr--;
if(empty(self::$nr_prims)) self::$nr_prims = $o->len;
if(defined('PRIMS_AUTOSAVE_COUNT') && $o->len - self::$nr_prims >= PRIMS_AUTOSAVE_COUNT)
{
$o->save(false, true);
self::$nr_prims = $o->len;
}
}
}
return $p;
}
/*!
* Adauga la lista interna de nr prime numerele prime <= $nr.
*
* Nota: Pentru valori mari ale $nr, dureaza mult...
* O($nr) = ($nr-$p)^3 (complexitatea)
*/
static protected function add_lte_prims($nr) // add less then or equal prims
{
$nr = abs($nr);
do $p = self::last(1); while($nr > $p);
return $p; // $nr <= $p
}
/*!
* Returneaza al $idx-lea nr prim.
*
* Nota: Primul numar prim are indexul 0 ($idx==0)
* Daca $idx depaseste count(), sunt generate nr prime neajuns
* pana la $idx.
*/
static function get($idx)
{
$o = self::getInst();
$l = $o->len;
if($idx >= $l) self::last($idx - $l + 1); else
if($idx < 0) {
$idx += $l;
if($idx < 0) die("List index out of bounds: $idx
\nMath::get()");
}
return $o->get_int_($idx);
}
/*!
* Returneaza produsul primelor $n nr prime.
* Daca $n < 0, se returneaza inversul produsului primelor -$n nr prime.
*/
function prod($n)
{
$o = &self::getInst();
if( $s = $n < 0 ) $n = -$n;
if( $n >= $o->len ) self::last($n - $o->len);
$p = 1;
while($n-- && is_finite($p)) $p *= $o->get_int($n);
return $s ? 1/$p : $p;
}
/*!
* Cauta $nr in lista interna de nr prime. (Binary search)
* Returneaza pozitia din lista, sau false, daca nu-l gaseste.
*
* O(log($nr))
*
* Atentie!
* Primul nr din lista e pe pozitia 0 !== false
*/
static function search($nr)
{
return self::getInst()->search(abs($nr));
}
/*!
* Cel mai mic nr prim mai mare sau egal cu $nr
* ($p >= $nr)
*/
static function ceil($nr)
{
$nr = abs($nr) ;
if($nr == 0 || $nr == 1) return false;
if($nr < 4) return $nr; // 2 || 3
$o = self::getInst();
$p = $o->last;
if($nr > $p) return self::add_lte_prims($nr);
if($nr == $p) return $p;
// if($nr < $p)
$p = $o->search_ceil($nr);
return $p === false ? false : $o->get_int_($p);
}
/*!
* Cel mai mare nr prim mai mic sau egal cu $nr
* ($p <= $nr)
*/
static function floor_idx($nr)
{
$nr = abs($nr) ;
if($nr == 0 || $nr == 1) return false;
if($nr == 2) return 0;
if($nr == 3) return 1;
$o = self::getInst();
$p = $o->last;
if($nr > $p)
{
// $q = self::add_lte_prims($nr);
$q = self::last(1);
if($nr < $q) return $o->len-2; // $p < $nr < $q
while($nr > $q) {
$p = $q;
$q = self::last(1);
}
$p = $q; // last is $p futher
}
if($nr == $p) return $o->len;
// if($nr < $p)
return $o->search_floor($nr);
}
function floor($nr)
{
$idx = $o->floor_idx($nr);
return $idx === false ? false : $o->get_int_($idx);
}
/*------------------------------------------------------------------------*/
static function div1($a, $b)
{ // 9.00 x 10000 | 0.090 x 1000
// greedy-iterativ
$r = 1;
for($i=$a<$b?$a:$b; $i>1; $i--) if(($a%$i==0)&&($b%$i==0)&&($r%$i!=0)) $r *= $i;
return $r;
}
static function div1a($a, $b)
{ // greedy-iterativ optimizat
$r = 1;
$min = $a<$b?$a:$b;
$i = 0;
while($p<=$min)
{
$p = self::get($i++);
if($a%$p==0 && $b%$p==0)
{
do {
$r *= $p;
$a = floor($a /$p);
$b = floor($b /$p);
} while($a%$p==0 && $b%$p==0);
$min = $a<$b?$a:$b;
}
}
return $r;
}
static function div2($a, $b)
{ // 0.20 x 10000 | 0.016 x 1000
// Euclid: recursiv-multiplicativ
// if(!$a) return $b; // $a > $b
if(!$b) return $a;
return self::div2($b, $a % $b);
}
static function div3($a, $b) // $a > 0 && $b > 0
{ // err x 10000 | 0.067 x 1000 // la numere mari apar probleme in PHP
// Euclid: recursiv-aditiv
if($a > $b) return self::div3($a - $b, $b);
if($a < $b) return self::div3($a, $b - $a);
return $a;
}
static function div4($a, $b) // cea mai rapida si mai frumoasa versiune
{ // 0.10 x 10000 | 0.015 x 1000
// Euclid: iterativ-multiplicativ
while($b) { $r = $a % $b; $a = $b; $b = $r; }
return $a;
}
static function div5($a, $b) // $a > 0 && $b > 0
{ // 0.27 x 10000 | 0.022 x 1000
// Euclid: iterativ-aditiv
// if(!$a ^ !$b) return 1;
// $a = abs($a); $b = abs($b);
while($a != $b) if($a>$b) $a=$a-$b; else $b=$b-$a;
return $a;
}
/*------------------------------------------------------------------------*/
/*!
* Algoritmul lui Euclid de aflare a
* celui mai mare divizor comun a doua numere, $a si $b
* Notatie: (a, b)
*/
static function divCom($a, $b)
{
if($a < $b) { $r = $a; $a = $b; $b = $r; }
// Euclid: iterativ-multiplicativ
while($b) { $r = $a % $b; $a = $b; $b = $r; }
return $a;
}
/*!
* Cel mai mic multiplu comun a doua numere, $a si $b
*
* Notatie: [a, b]
*/
static function mulCom($a, $b)
{
// [a,b] = (a*b) / (a,b)
return (int)( $a*$b / self::divCom($a, $b) );
}
/*------------------------------------------------------------------------*/
/*!
* Cel mai mare divizor comun.
*
* Sintaxa:
* CMMDC(mixed $arr[, mixed $arr1[, mixed $arr2...]])
*/
static function CMMDC($arr)
{
if(is_array($arr))
{
sort($arr, SORT_NUMERIC); // daca toate sunt pozitive si exista 1, nu se vor mai parcurge celelalte elemente
$r = array_pop($arr);
foreach($arr as &$v)
{
if($r == 1 || $r == -1) break;
$r = self::divCom($r, self::CMMDC($v));
}
$arr = $r;
}
if(func_num_args()==1) return $arr;
for($i=1; $i < func_num_args(); $i++)
{
if($arr == 1 || $arr == -1) break;
$v = func_get_arg($i);
$arr = self::divCom($arr, self::CMMDC($v));
}
return $arr;
}
/*!
* Cel mai mic multiplu comun.
*
* Sintaxa:
* CMMMC(mixed $arr[, mixed $arr1[, mixed $arr2...]])
*/
static function CMMMC($arr)
{
if(is_array($arr))
{
$r = array_pop($arr);
foreach($arr as &$v) $r = self::mulCom($r, self::CMMMC($v));
$arr = $r;
}
if(func_num_args()==1) return $arr;
for($i=1; $i < func_num_args(); $i++)
{
$v = func_get_arg($i);
$arr = self::mulCom($arr, self::CMMMC($v));
}
return $arr;
}
/*------------------------------------------------------------------------*/
/*!
* Verifica daca numarul $n este prim
* O($n) <= 1 (complexitate)
*/
static function isPrim($nr)
{
if($nr == 2) return true; // Unicul numar prim par
if(~$nr&01 || $nr == 0 || $nr == 1 || $nr == -1) return false; // 0, +-1 si nr pare nu sunt prime
$nr = abs($nr); // $nr se precauta ca nr pozitiv
$o = self::getInst(); // lista interna de numere prime
$p = $o->last;
// Daca este mai mic decat ultimul prim din lista interna
if($nr <= $p) { // se cauta in lista interna de nr prime
return self::search($nr) !== false;
}
// $nr > $p: $nr este in afara listei (mai mare)
$lim = floor(sqrt($nr));
$p = $o->reset;
while($p !== false) {
if($nr % $p == 0) return false;
if($p > $lim) return true;
$p = $o->next;
}
// Daca lista de nr prime e prea mica, // se cauta folosind algoritmul liniar
do {
$p = self::last(1); // adaugam un element la lista de nr prime
if($nr % $p == 0) return false;
} while($p <= $lim);
// In sfarsit, daca nu se imparte la nimic, $nr este prim
return true;
}
/*!
* Aplicarea teoremei de baza a aritmeticii:
* Orice numar intreg (>1) este prim sau
* se descompune in produs de factori primi.
* Aceasta descompunere se numeste forma canonica a numarului intreg.
*
* Fie $n = pow(p1,a1)*pow(p2,a2)*...*pow(pn,an).
* @return array(p1=>a1, p2=>a2, ..., pn=>an);
*/
static function canonic($nr)
{
if($nr == 0 || $nr == 1 || $nr == -1) return array(); // nici prim, nici compus
$r = array();
if($nr<0){ $r[-1] = 1; $nr = -$nr; }
if(self::isPrim($nr)){ $r[$nr] = 1; return $r; } // $nr este prim sau...
// se descompune in produs de factori primi
// self::getInst(); // se keama in self::isPrim()
$l = self::last(0);
$o = &self::$inst;
$p = $o->reset;
while($p !== false) {
while($nr % $p == 0) { $r[$p]++; $nr = floor($nr/$p); }
if($nr == 1) return $r;
$p = $o->next;
}
do {
$p = self::last(1);
while($nr % $p == 0) { $r[$p]++; $nr = floor($nr/$p); }
}
while($nr>1);
return $r;
}
/*!
* Functia inversa a canonic($n)
*/
static function can2nr($c)
{
$r = 1;
foreach($c as $pr=>$pw) while($pw--) $r *= $pr;
return $r;
}
/*!
* Formeaza codul HTML al formei canonice a nr $n.
* $n poate fi numarul descompunerea sa (array)
*
* @return if($array) array(p1=>p1^a1, p2=>p2^a2, ..., pn=>pn^an); /
* else p1^a1 * p2^a2 * ... * pn^an
*/
static function canHTML($nr, $array=false)
{
if(!is_array($nr)) $nr = self::canonic($nr);
foreach($nr as $pr=>&$pw) $pw = "$pr".($pw>1?"$pw":'');
return $array ? $nr : implode(' * ', $nr);
}
/*!
* Suma divizorilor naturali ai numarului $nr
*/
function sum_div($nr)
{
}
/*!
* Numarul divizorilor naturali ai numarului $nr
*/
function nr_div($nr)
{
}
/*!
* Cantitatea ne numere reciproc prime cu $nr
* si mai mici decat $nr
*/
function lt_nr_prims($nr) // less then $nr prims
{
}
}
/*------------------------------------------------------------------------------------------*/
?>