Найти наибольший нетривиальный делитель натурального числа

<?php
   
  /* Наибольший нетривиальный делитель натурального 
 числа --- это наибольшее натуральное число на которое 
 делится рассматриваемой нами число . Естественно , что 
 любое натруальное число делится само на себя и на единицу 
 нацело . Именно эти два числа --- само число и единица ---
 являются тривиальными делителями, и их мы не рассматриваем.
 Будем рассуждать следующим образом : 
 1) Рассматриваемое нами число может иметь один , два
 и более натуральных делителя , на которых оно делится без 
 остатка . Значит, мы должны придумать условие , которое бы
 отражало суть нашего деления. То есть получается , что при 
 делении на любой нетривиальный делитель у нас число делится
 нацело без остатка . То есть явно использовать  $a % $i == 0 
 Наше число $a делим на $i  и возвращаем остаток 
 (остаток от деления получается матемтической операцией % ),
 который должен равняться нулю. Мы должны перебрать все возможные
 делители $i , которые делятся без остатка на наше число $a .
 И выбрать наибольший .
 */
// Записываем наше число 
$a=20;
// Первое число берем два , один и ноль не подходят. На ноль делить 
//нельзя , а единица -это тривиальный делитель.
 $i=2;
// Теперь пишем цикл . Мы должны перебрать все делители от 2 и далее
// которые делятся без остатка .
  echo "Это результат первого кода : ","<BR>";
 while (($a % $i ) == 0 )
 { 
 echo $i , "<BR>";
     $i++;
 }
  echo "А теперь другой код : ","<BR>";
// Отлично ! Программа работает , но здесь есть недочёт 
// программа работает пока условие (($a % $i ) == 0) истинно, 
// то есть, если число $a=26 , а $i=2 , то всё отлично делится
// без остатка , условие выполнилось то есть  условие  возвращает нам
// TRUE и цикл прекратился уже при $i=3 ,так как уже будет остаток,
// равный 2 . 
// Всё хорошо , но задачу мы не решили . Мы должны найти 
// наибольший делитель . Как исправить код ?
// Вот решение : 
// Создадим массив ( он необходим для записи всех делителей):
$array=array();
// создадим массив в цикле while. А здесь запишем чему равен начальный элемент: 
$e=0;
// И создадим массив с неизвестным количеством элементов
$array=array();
// Начинаем работу  программы: 
   
for ($k=0 ; $k<$a ;$k++)
{
      
 while ( (($a % $i ) == 0 ))
     // Мы должны сделать так чтобы количество 
     // элементов массива равнялось количеству индексов  
     //массива : 
          
         { 
                  //Заполним массив делителей , их количество заранее
                  // неизвестно: 
			   $array[$e].$i;
                   //увеличиваемномер элемента массива на единичку
               $e++;
             // Выводим значение переменных $i и $k (вывод $k нужен
                          //     для  понимания работы цикла) 
             echo  "Chislo  i:", $i ,"&nbspChislo k:",$k, "<BR>";
             // Если оператор  break  убрать , то цикл будет выполнятся
                         //бесконечно . Почему ? 
             // Ответ : пока  условие цикла while истинно , то тело цикла 
                          //  будет выполнятся бесконечно
             // а это потому , что переменная $i здесь неизменна , а
                        // меняется вне цикла while
             break; 
         }
     $i++; 
}
// Всегда нетривиальный делитель по порядку на единичку меньше ,
//чем само число (которое является тривиальным делителем) , как 
//последнее в порядке всех делителей .
// Другими словами наибольший нетривиальный делитель
// по порядку записи в массиве стоит предпоследним , то есть 
// ключ массива равен $e-1 : 
 
 echo $array[$e-1]   , "&nbspNaibolshii netrivialnii delitel" ,"<BR>";
 
   
 ?>    
vedro-compota's picture

задача плюсом отмечена в списке не была - но раз взялись, то решайте её. Это полезно.
Создайте отдельную заметку "нетривиальный делитель" в этом разделе (где и объясните что это такое и затем уже сошлитесь "отсюда туда")

_____________
матфак вгу и остальная классика =)

vedro-compota's picture

Мы должны найти
// наибольший делитель . Как исправить код ?

прежде всего необходимо иное условие завершения перебора делителей, в данный момент вы решили задачу поиска 1-ого нетревиального делителя (а не последнего, который и нужен).

_____________
матфак вгу и остальная классика =)

На самом деле задача поиска наименьшего нетривиального делителя не решена.

$a=15;
$i=2;
while (($a % $i ) == 0 )
 {
 echo $i , "<BR>";
     $i++;
 }

Если \$a не делится на 2, то тело цикла while не будет выполнено ни разу.

Произведение наименьшего нетривиального делителя числа \$a и наибольшего нетривиального делителя числа \$a равно числу \$a.

Можно исправить код, изменив условие цикла.

<?php

$a = 13733;	// наше число
$i = 2;	// Мы будем перебирать все числа, начиная с 2,
// до того момента, как деление будет выполнено без остатка.

while ( ($a % $i ) != 0 )
	$i++;

if ($i == $a)	
	echo "Это простое число.\n";
else
	echo "Наибольший нетривиальный делитель равен ", $a / $i, "\n";

?>    
vedro-compota's picture

  • 1) Задача действительно не решена ещё (насколько я знаю - уведомления об окончательном решении не получал.) Насколько я понимаю, она была "в процессе" =)
  • 2) При рассуждениях прошу придерживаться таких соображений - чтобы повысить читаемость.

_____________
матфак вгу и остальная классика =)

OK. Знаки доллара поставил.

vedro-compota's picture

спасибо)

_____________
матфак вгу и остальная классика =)

vedro-compota's picture

for ($k=2 ; $k<=$a ;$i++)

несогласованные условия. такой цикл никогда не закончится. почему?

_____________
матфак вгу и остальная классика =)

fgh's picture

Да , так как \$k всегда меньше \$a , а подкручивается только счётчик \$i.

vedro-compota's picture

Что делает цикл:

for ($k=0 ; $k<$a ;$k++)
{

?? Объясните пожалуйста.

_____________
матфак вгу и остальная классика =)

fgh's picture

Данный цикл , осуществляет запуск по новой вложенного цикла while , задача цикла

for

увеличи вать значение :

  $i  

и запуск цикла while при другом значении:

 $i
vedro-compota's picture

увеличи вать значение :

$i

и запуск цикла while при другом значении:

$i

это бессмыссленный ответ. Я и сам вижу код.
Скажите мне - какой смысл имеет цикл относительно построения алгоритма?
В том-то и проблема, что в данный момент эта конструкции просто "запускает" внутрениий сколько-то раз. но зачем?

_____________
матфак вгу и остальная классика =)

Интересно, что цикл while здесь функционирует как условный оператор if.

<?php

// наше число 
$a=143345234;
echo "Число $a состоит из следующих простых множителей,\n";

$array=array();	// массив для записи всех множителей
$e=0;	// индекс
    
for ($k=2 ; $k<=$a ;$k++)
{
	while ( ( $a % $k ) == 0 )
	{ 
		$array[$e] = $k;
		$e++;
		$a = $a / $k;	//эта строка добавлена
		$k--;		//эта строка добавлена
		break; 
         }
}
echo "количество которых  ", $e, ":\n";

foreach ($array as $value)
	echo "$value  ";

?>
  
vedro-compota's picture

а потому он конструктивно избыточен - тут при любом стиле достаточно одного цикла, судя по всему.
Вложенность вообще не нужна.

_____________
матфак вгу и остальная классика =)

vedro-compota's picture

на самом деле решение вашей задачи начинается с этой (в некотором смысле) - относительно перебора делителей.

В данный момент вы "разогнали" и комментарии до изрядного размера, но при этом в Вашем рассуждении отсутствуют комментарии к структурам двух циклов:
for ($k=0 ; $k {

while ( (($a % $i ) == 0 ))
- вы должны чётко формулировать (и осозновать!) - для чего вы создаёте очередной цикл.

_____________
матфак вгу и остальная классика =)

Кстати, из второй части приведённого решения можно сделать программу
для разложения натуральных чисел на простые множители.

<?php

// наше число 
$a=143345234;
echo "Число $a состоит из следующих простых множителей,\n";

$array=array();	// массив для записи всех множителей
$e=0;	// индекс
    
for ($k=2 ; $k<=$a ;$k++)
{
	if ( ( $a % $k ) == 0 )
	{ 
		$array[$e] = $k;
		$e++;
		$a = $a / $k;
		$k--;
	}
}
echo "количество которых  ", $e, ":\n";

foreach ($array as $value)
	echo "$value  ". $value. "\n";

?>
fgh's picture

Ух ты интересно...спасибо ))) сейчас изучаю как реализовывался массив с

foreach  

А задачу надо мне дорешать с нового листа : решение с чистого листа