Сверхсоставные числа на PHP

Сверхсоставные числа (Highly composite numbers) ещё называют "анти-простыми" (anti-prime), суть в том, что сверхсоставное натуральное число имеет большее количество делителей, чем любое меньшее его натуральное число (Вики).

Если не вычислять примитивно делители каждого числа заново, остаётся только "решетоподобный" алгоритм с составлением списка делителей и последующим его анализом, по крайней мере, ничего лучшего я придумать не смог.

Первые 30 сверхсоставных чисел, "помещающихся" в границу поиска до 111000, показанный ниже скрипт найдёт довольно быстро, для удобства числа выводятся в браузер по мере их вычисления, примерно как здесь.

Дальше, разумеется, всё зависит от количества памяти, которое Вы можете себе позволить выделить. Проверено на локальном хосте под Denwer в старенькой 32-разрядной системе.

<?php
 set_time_limit (0);
 ini_set('output_buffering','on');
 ini_set('zlib.output_compression', 0);

 $arr = array();
 $n = 111000; 
  //граница поиска; на PHP_INT_MAX памяти не хватит :)
 array_fill (0, $n, 0);
 
 ob_implicit_flush();
 for ($i = 1; $i < $n; $i++) {
  for ($j = $i; $j < $n; $j+=$i) $arr[$j]++;
 }
 $max_divisors = 0;
 for ($i = 1; $i < $n; $i++) {
  $divisor_count = $arr[$i];
  if ($divisor_count > $max_divisors) {
   echo $i.'<br>';
   ob_flush();
   usleep(100000);      
   $max_divisors = $divisor_count;
  }
 }
 
 ob_end_clean();
?>

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

<?php
 set_time_limit (0);
 ini_set('output_buffering','on');
 ini_set('zlib.output_compression', 0);

 function countDivisors ($n) {
  if ($n < 2) return 1;
  $cnt = 2; // 1 and n
  for ($i = 2; $i <= $n/2; $i++) if ($n%$i == 0) $cnt++;
  return $cnt;
 }
 
 ob_implicit_flush();
 $maxDiv = $cnt = 0;
 for ($n = 1; $n <= PHP_INT_MAX; $n++) {
  $d = countDivisors ($n);
  if ($d > $maxDiv) {
   echo $n.'<br>';
   ob_flush();
   usleep(100000);
   $maxDiv = $d;
   $cnt++;
  }
 }
 ob_end_clean();
?>

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

18.05.2019, 11:55 [1315 просмотров]