Сервис для проверки числа на простоту и поиска целых делителей числа
Тема простых чисел у меня всплывает достаточно регулярно, думаю, для проверки одного числа особой эффективности не нужно, достаточно не слишком тупого перебора.
Вводимое число ограничено 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> </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 [11914 просмотров]