Factoring.php

  1. <?php
  2. /*
  3. Factoring.php — Francisco Cascales — 2017-XII-8
  4. Versión más rápida en "Factoring.java"
  5. */
  6.  
  7. //ini_set('display_errors', 1);
  8. //error_reporting(E_ALL);
  9.  
  10. include "Primes.php";
  11.  
  12. class Factoring {
  13.  
  14. /*
  15. Usa las clases de Java: Factoring y Primes
  16. porque es mucho más rápido que la versión PHP
  17. */
  18. public static function throughJava($number) {
  19. $number = self::cleanNumber($number);
  20. $number = escapeshellarg($number);
  21. $result = shell_exec("java Factoring $number");
  22. $result = trim($result, "\n");
  23. return $result;
  24. }
  25.  
  26. /*
  27. Versión texto de la factorización texto
  28.  
  29. 360 --> 2^3*3^2*5
  30. 12 --> 2^2*3
  31. 20 --> 2^2*5
  32. 17 --> 17
  33. */
  34. public static function textualize($number) {
  35. if (!is_numeric($number)) return "No es un número";
  36. $factors = self::gmpFactoring($number);
  37. if ($number != self::defactoring($factors)) return "Error al calcular";
  38. $text = "";
  39. foreach($factors as $factor=>$exponent) {
  40. if (!empty($text)) $text .= '*';
  41. $text .= $factor;
  42. if ($exponent>=2) $text .= "^$exponent";
  43. }
  44. return $text;
  45. }
  46.  
  47. /*
  48. Factoriza el número indicado
  49. Desde 1 hasta 965_211_250_482_432_409 (LAST_PRIME^2)
  50.  
  51. 360 --> array(2=>3, 3=>2, 5=>1)
  52. 12 --> array(2=>2, 3=>1)
  53. 20 --> array(2=>2, 5=>1)
  54. 17 --> array(17=>1)
  55. */
  56. public static function gmpFactoring($number) { // GMP = GNU Multiple Precision
  57. $result = $number;
  58. $root = gmp_sqrt($number);
  59. if (gmp_cmp($number, 0) <= 0) return array(); // Negative or zero
  60. elseif (gmp_cmp($number, 1) == 0) return array(1=>1); // One
  61. elseif (gmp_cmp($root, Primes::LAST_PRIME) > 0) return array(); // Overflow
  62. $primes = new Primes();
  63. $factors = array();
  64. while ($primes->hasNext()) {
  65. $prime = $primes->next();
  66. if (gmp_cmp($result, 1) == 0) break;
  67. elseif (gmp_cmp($prime, $root) > 0) {
  68. $factors[gmp_strval($result)] = 1;
  69. break;
  70. }
  71. $exponent = 0;
  72. for(;;) {
  73. list($quotient, $remainder) = gmp_div_qr($result, $prime);
  74. if (gmp_cmp($remainder, 0) != 0) break;
  75. $exponent++;
  76. $result = $quotient;
  77. $root = gmp_sqrt($result);
  78. if ($exponent > 60) break; // Avoid infinite iterations
  79. }
  80. if ($exponent >= 1) $factors[$prime] = $exponent;
  81. }
  82. $primes->close();
  83. return $factors;
  84. }
  85.  
  86. /*public static function division($dividend, $divisor){
  87. ////return ($dividend - $dividend % $divisor) / $divisor; // like intdiv php7
  88. ////return floor($dividend / $divisor);
  89. $quotient = (int)($dividend / $divisor);
  90. $remainder = $dividend % $divisor;
  91. return array($quotient, $remainder);
  92. }*/
  93.  
  94. /*
  95. Calcula el resultado de los factores
  96.  
  97. array(2=>3, 3=>2, 5=>1) --> 360
  98. array(2=>2, 3=>1) --> 12
  99. array(2=>2, 5=>1) --> 20
  100. array(17=>1) --> 17
  101. */
  102. public static function defactoring($factors) {
  103. if (empty($factors)) return 0;
  104. $number = 1;
  105. foreach ($factors as $factor=>$exponent) {
  106. $number *= pow($factor, $exponent);
  107. }
  108. return $number;
  109. }
  110.  
  111. //---------------------------------------------
  112. // HELPERS
  113.  
  114. /*
  115. Texto a Markdown
  116. para mostrarla en el bot de Telegram
  117.  
  118. 2^3*3^2*5 --> *2*^3×*3*^2×*5*
  119. 2^2*3 --> *2*^2x*3*
  120. 2^2*5 --> *2*^2x*5*
  121. 17 --> *17*
  122. */
  123. public static function toMarkdown($text) {
  124. $markdown = '';
  125. $items = explode('*', $text);
  126. foreach ($items as $item) {
  127. $parts = explode('^', $item);
  128. if (!is_numeric($parts[0])) return "💩 $parts[0]";
  129. if (!empty($markdown)) $markdown .= '×';
  130. $markdown .= "*$parts[0]*";
  131. if (count($parts) == 2) $markdown .= "^$parts[1]";
  132. }
  133. return $markdown;
  134. }
  135.  
  136. /*
  137. Texto a HTML
  138. para mostrarla en la página web
  139.  
  140. 2^3*3^2*5 --> 2<sup>3</sup>&times;3<sup>2</sup>&times;5
  141. 2^2*3 --> 2<sup>2</sup>&times;3
  142. 2^2*5 --> 2<sup>2</sup>&times;5
  143. 17 --> 17
  144. */
  145. public static function toHTML($text) {
  146. $markdown = '';
  147. $items = explode('*', $text);
  148. foreach ($items as $item) {
  149. $parts = explode('^', $item);
  150. if (!is_numeric($parts[0])) return $parts[0];
  151. if (!empty($markdown)) $markdown .= '&times;';
  152. $markdown .= $parts[0];
  153. if (count($parts) == 2) $markdown .= "<sup>$parts[1]</sup>";
  154. }
  155. return $markdown;
  156. }
  157.  
  158. /*
  159. Deja sólo las cifras
  160. */
  161. public static function cleanNumber($text) {
  162. $result = '';
  163. $chars = str_split($text);
  164. foreach ($chars as $char) {
  165. if ($char == '') continue;
  166. if (strpos("0123456789", $char) !== false) $result .= $char;
  167. }
  168. return $result;
  169. }
  170.  
  171. }
  172.  

Proinf.net