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

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

Вводимое число ограничено 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);

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

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

Полный исходник:

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
 <meta content="text/html; charset=Windows-1251" http-equiv="content-type">
 <title>Сервис для проверки числа на простоту и вывода делителей числа</title>
</head>
<body>

<?php

 function trimall($string) { return trim(preg_replace("/\s+/"," ",$string)); }
 
 function magic ($path) {
  @ini_set('magic_quotes_runtime', '0'); @ini_set('magic_quotes_sybase', '0');
  if (@get_magic_quotes_gpc()=='1') $path=stripslashes($path);
  return $path;
 }
 
 $params = array ('n','div','action');
 while (list($num,$var) = each($params)) {
  if (!empty($_GET[$var])) $$var = trimall(htmlspecialchars(magic($_GET[$var])));
  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" value="1"'.($div==1?' checked':'').'>'.
     ($div==1?'Выключите, если не нужно':'Включите, если нужно').'
    </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>

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

комментарии (0)

01.12.2013, 17:24; рейтинг: 9048