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