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