БлогNot. Сервис для проверки числа на простоту и поиска целых делителей числа

Сервис для проверки числа на простоту и поиска целых делителей числа

Тема простых чисел у меня всплывает достаточно регулярно, думаю, для проверки одного числа особой эффективности не нужно, достаточно не слишком тупого перебора.

Вводимое число ограничено 10 цифрами, его максимальное значение зависит от разрядности системы, в которой установлен скрипт. Так, 9999999999 в 32-битной системе, к сожалению, превратится в 2147483647 (максимально возможное целое со знаком, которое "влазит" в 32 бита; кстати, это простое число).

А вот максимальное знаковое целое значение для 64-х битных систем - 9223372036854775807, так что можно изменить ограничения на размер поля ввода числа:

<input type="text" name="n" maxlength="10" size="10" value="'.$n.'">

- заменить здесь число 10 на 19.

Для экономии серверного времени также в режиме "Выводить целые делители числа" не отображаются делители, большие квадратного корня из числа, например, для значения 999999999 делитель 333333333 показан не будет. Если хотите это изменить - замените в коде значение переменной $SEARCH_LIMIT с

$SEARCH_LIMIT = floor(sqrt($n));

на

$SEARCH_LIMIT = floor($n/2);

и поставьте скрипт к себе на хостинг :)

 Скрипт в работе

Вот исходный текст скрипта в виде файла .php:

<!DOCTYPE html>
<html lang="ru">
<head>
 <meta charset="utf-8">
 <title>Сервис для проверки числа на простоту и вывода делителей числа</title>
</head>
<body>
<p><a href="http://blog.kislenko.net/show.php?id=1077">Страница скрипта</a></p>

<?php

 function trimall($string) { return trim(preg_replace("/\s+/",'',$string)); }
 
 $params = array ('n','div','action');
 foreach ($params as $num=>$var) {
  if (!empty($_GET[$var])) $$var = trimall(htmlspecialchars($_GET[$var],ENT_QUOTES,'UTF-8'));
  else $$var = '';
 }
 $n=intval($n);
 if (!empty($n) and $n<0) $n=-$n;

 echo '
 <form name="f1" method="get" action="'.$_SERVER['PHP_SELF'].'">
  <table align="center" border="0" cellpadding="4" cellspacing="0">
   <caption>Проверка числа на простоту и целые делители числа</caption>
   <tr>
    <td>Введите натуральное число:</td>
    <td>
     <input type="text" name="n" maxlength="10" size="10" value="'.$n.'">
    </td>
   </tr>
   <tr>
   <tr>
    <td>Выводить целые делители числа:</td>
    <td>
     <input type="checkbox" name="div" id="div_id" value="1"'.($div==1?' checked':'').'><label for="div_id">'.
     ($div==1?'Выключите, если не нужно':'Включите, если нужно').'</label>
    </td>
   </tr>
   <tr>
    <td>&nbsp;</td>
    <td>
     <input type="submit" name="action" value="Проверить"> 
     <a href="'.$_SERVER['PHP_SELF'].'?div=0&n=">Очистить</a>
    </td>
   </tr>
  </table>
 </form>'."\n";

 if (!empty($action)) { 
  echo '<table align="center" border="0" cellpadding="4" cellspacing="0"><tr><td>Получено число: '.$n."\n";
  $prime=1;
  $divs=array();
  if ($n<2) {
   $prime=0;  
   echo '<br>'.($n==0?'Ноль':'Единица');
  }
  else {
   $SEARCH_LIMIT = floor(sqrt($n)); //floor($n/2);
   if ($div) {
    for ($i=2; $i<=$SEARCH_LIMIT; $i++) if ($n%$i==0) { 
     $prime=0; 
     $divs[]=$i;
    }
   }
   else {
    if ($n==2) $prime=1;
    else if ($n%2==0) $prime=0;
    else if ($n<6) $prime=1;
    else for ($i=3; $i<=$SEARCH_LIMIT; $i++) if ($n%$i==0) { $prime=0; break; }
   }
   echo '<br>'.($prime? 'Простое' : 'Составное').' число';
   if (!$prime and $div) {
    echo '<br>Делители: ';
    foreach ($divs as $d) echo $d.' ';
    echo '<br>Верхняя граница поиска: '.$SEARCH_LIMIT;
   }
  }
  echo '</td></tr></table>'."\n";
 }
?>
</body></html>

01.12.2013, 17:24 [11320 просмотров]


теги: php сервис числа