Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > PHP: Общие вопросы > В чём ошибка в этом скрипте?


Автор: MuradK 14.5.2005, 14:50
Код

<? 
for ($i = 0; $i < 100; ++$i)
{ for ($j = 0; $j < $i; ++$j)
{ 
if (($i%$j) !=0)
continue;
else
{ 
$flag=true;
      break;
}
}
if (!$flag)
{ 
echo ($i);
echo (" ");
}
$flag=false;
}
?>


Выодится нуль вместо простых чисел до ста smile

Автор: Mal Hack 14.5.2005, 14:57
В алгоритме.
Код
<?php

 for ($i = 1; $i < 100; ++$i)
  {
   $flag = FALSE;

   for ($j = 2; $j < floor($i/2); $j++)
    {
     if ( ( $i % $j ) != 0)
      {  continue;  }
     else
      {
       $flag = TRUE;
       break;
      }
    }

   if( $flag == FALSE )
    { print $i . "<br>"; }
  }

?>

Автор: MuradK 14.5.2005, 15:04
Danke lehrmeister smile
А что такое "floor"?
Если не затруднит...

Автор: Mal Hack 14.5.2005, 15:08
Округление, но в меньшую степень, т.е.
floor(4.9) - 4.
http://php.net/floor.

Автор: MuradK 14.5.2005, 15:34
ОК!
Но ведь 4 не простое число smile

Автор: Mal Hack 14.5.2005, 15:36
Цитата(MuradK @ 14.5.2005, 16:34)
Но ведь 4 не простое число smile

Я в качестве примера работы floor показал.

Автор: MuradK 14.5.2005, 20:31
Понятно. Спасибо.

Автор: GorD 22.5.2005, 20:01
Хоть 100 и не такое уж большое число, но для ускорения поиска целых чисел в коде
Mal Hack'a можно заменить строчку

Код

for ($j = 2; $j < floor($i/2); $j++)


на строчку

Код

for ($j = 2; $j < sqrt($i); $j++)



(я новичок в PHP, поэтому я еще не разобрался со всеми функциями, поэтому взял функцию из С. Короче говоря, $j можно ограничить не половиной $i, а квадратным корнем из $i.)

Автор: Mal Hack 22.5.2005, 20:13
GorD
ты не прав. Смотри. Что такое простое число. То, которое делится только на себя и на 1.
Т.е. мы идем в цикле с 1 до 100 (число делим на 2, 3, 4). Но смысл на идти дальше 50, т.к. мы просто повторяться будем. т.к. если 100 / 70 будет одно из чисел от 1 до 50. Поэтомы мы и делим только на число от 1 до 50.
sqrt дает совсем другой результат. При нем мы пойдем только до 10, при этом проинорировав 20.

Автор: GorD 22.5.2005, 20:35
А, да, я маленько перепутал. Я вспомнил пример, когда надо узнать, простое ли данное число вот код:

к примеру, это число $p

Код

<?php
 $flag=FALSE;
 for ($i = 1; $i < sqrt($p); ++$i)  if ($p%$i==0) {ehco $p."  составное"; break; $flag=TRUE; }
 if ($flag=FALSE) ehco $p."  простое";

Автор: Bikutoru 27.5.2005, 15:03
Цитата
Ты не прав. Смотри. Что такое простое число. То, которое делится только на себя и на 1.
Т.е. мы идем в цикле с 1 до 100 (число делим на 2, 3, 4). Но смысл на идти дальше 50, т.к. мы просто повторяться будем. т.к. если 100 / 70 будет одно из чисел от 1 до 50. Поэтомы мы и делим только на число от 1 до 50.
sqrt дает совсем другой результат. При нем мы пойдем только до 10, при этом проинорировав 20.


По-моему, ошибаешься ты... Смотри, если a=b*c, то
1. либо b=c=sqrt(a)
2. либо ((b < sqrt(a)) || (c < sqrt(a)) (иначе просто b*c > sqrt(a)*sqrt(a) = a ))

Так что, sqrt(a) - это здравая мысль _при больших числах_

Автор: Mal Hack 27.5.2005, 15:07
Цитата(Bikutoru @ 27.5.2005, 16:03)
По-моему, ошибаешься ты... Смотри, если a=b*c, то
1. либо b=c=sqrt(a)
2. либо ((b < sqrt(a)) || (c < sqrt(a)) (иначе просто b*c > sqrt(a)*sqrt(a) = a ))

Так что, sqrt(a) - это здравая мысль _при больших числах_

Честно не фига не понял....
то что мы должны идти до половины числа - это точно.

Автор: Bikutoru 27.5.2005, 15:13
Если число может быть представлено как произведение двух сомножителей, то один из них (сомножителей) _обязательно_ меньше или равен квадратному корню исходного числа, а второй сомножитель _обязательно_ больше или равен квадратному корню исходного числа. Иначе просто не может быть!

Автор: Irokez 27.5.2005, 15:14
Цитата(Mal @ 27.5.2005, 15:07)
Честно не фига не понял....
то что мы должны идти до половины числа - это точно.


Bikutoru прав, надо идти до корня от числа, т.к. число если оно не простое имеет как минимум один делитель отличный от него самого и единицы, если такой делитель существует то он будет располагаться на числовой прямой от единицы до корня данного числа

Автор: Mal Hack 27.5.2005, 15:26
Но ведь коренб может быть дробным.

Автор: Irokez 27.5.2005, 15:29
округляем, ceil()

Автор: Bikutoru 27.5.2005, 15:36
Цитата
Но ведь коренб может быть дробным.

Значит один из сомножителей меньше корня исходного числа.

Вот исходная программа "по последнему слову" этой темы. Вроде нормально работает, хоть кое-где корень действительно дробный...
Код

for ($i = 0; $i < 100; ++$i)
{
     echo "<Br>" . $i;
     $max = sqrt($i);
     $flag = false;
     for ($j = 2; $j <= $max ; ++$j)
     {
          if ($i%$j)
               continue;

          $flag = true;
          break;
     }

     if (!$flag)
          echo "+";
}

Автор: Mal Hack 27.5.2005, 15:36
Я как-то логики понять не могу. smile

Автор: Irokez 27.5.2005, 15:43
Цитата(Mal @ 27.5.2005, 15:36)
Я как-то логики понять не могу. smile

1) У непростого числа (N) есть хотя бы два делителя (A и B), их произведение дает нам наше число (N = A * B)
2) Если A = B, тогда A = sqrt(N);
3) Если A > B, тогда B < A < sqrt(N);
4) аналогичные рассуждения и про В
Добавлено @ 15:47
а не, вот так:
1) У непростого числа (N) есть хотя бы два делителя (A и B), их произведение дает нам наше число (N = A * B)
2) Если A = B, тогда A = sqrt(N);
3) Допустим что и A > sqrt(N) и B > sqrt(N), тогда, A * B > sqrt(N) * sqrt(N) > N, а это невозможно, следовательно либо A < sqrt(N) либо B < sqrt(N)

Автор: Mal Hack 27.5.2005, 15:48
Все понял. Спасибо. Обоим + за разъяснения.
GorD + за правильное решение, которое я отверг smile Сорри.

Автор: borisvolfson 30.5.2005, 18:26
Mal Hack
Тогда можно округлять в большую сторону. Вообще, когда речь о поиске простых чисел, то вариант с поиском до половины в полне проканывает. Кстати, писать лучше так:
Код

for ($i = 2; $i*$i <= n; $i++)
{
  ... 
}

Тогда не будет и проблем с округлением.

ЗЫ Для поиска всех простых чисел в заданном диапазоне обычно используют решето Эратосфена, а не проверку на простоту... smile

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)