Как найти все делители числа php

If we try to find all the divisors D(array) of a number N, then the divisors of each d in D is also automatically calculated in the calculation of D. Is there a way that we can find all the divisors of a number N by finding the divisors of all its divisors, and then finally summing them up. Obviously, there is a way but I want a way which doesn’t have repetitive calculation. I think this can be done by recursion, but I am not getting how to proceed. I am providing my implementation of calculating all the divisors of a number N. I want to extend it in a way that, while calculating the divisors of N, I also calculate the divisors of all the divisors(and save them). Finally, I can add them up and get what I wanted. But in the whole process the beneficial point is that I also got the divisors of all divisors without any extra effort(ie, repetitive calculation).

function divisors_of_a_number($n)//returns all the divisors of a number in an unsorted array
{
$i=1;
$s=bcsqrt($n);
while($i<=$s)
{
if(!(bcmod($n,$i)))
{
    $a[]=$i;
    if($i!=$s)
    $a[]=bcdiv($n,$i);
}
++$i;
}
return $a;
}

Here’s an example to clarify this-
Say, N is 6. So divisors of N are- {1,2,3,6}. Now, ‘3’ is a divisor of N. It means that the numbers which divide ‘3’(ie, its divisors) will also divide N. Thus, we can say the divisors of ‘3’ will divide N. Similarly, for every divisor d of N, we can say that the divisors of d are also the divisors of N. So, when we compute the divisors for N, we compute all the divisors of, each of its divisor d. I want a way that while computing divisors for N=6, I get the divisors of {1},{2},{3} also(and save them) without extra computation( because all of them are already being computed for 6).

As a live example, if N=20, I want my function to work in a sense that it returns an array of arrays.
Now the outer array contains the keys as the Divisors of 20 ie, the keys will be {20,10,5,4,2,1}.
Now, associated with these keys are arrays. Each of these arrays are the divisors of their respective keys. Now, if I take the intersection of elements of all the inner arrays, I will get the divisors of 20. It means, all the elements are calculated even if I only calculate the divisors of 20. But, I want to get the required output without any extra computation. Extra computation means that I obviously can calculate the divisors of divisors of 20 and return the array of arrays. But, I don’t want to do it because the I know «the divisors of all the divisors of 20 are themselves calculated while the calculation of divisors of 20». I hope this clarifies all the things.

    $x = 66928;
$y = 66992;

$c_a = [];
$c_b = [];
$d = 1;
while ($d_a <= $x) {
if (is_int($x / $d)) $c_a[] = $d;
$d++;
}
$d = 1;
while ($d_b <= $y) {
if (is_int($y / $d)) $c_b[] = $d;
$d++;
}
echo count($c_a);
echo count($c_b);

// Output
$c_a = 20;
$c_b = 20;

Решение

<?php
$a = 66928;
$b = 66992;
$min = ($a < $b ) ? $a : $b;
$commomn_factors_count = 0;
for ($i = 1; $i < $min/2; $i++) {
if (($a%$i==0) && ($b%$i==0)) {
$commomn_factors_count++;
}
}
var_dump($commomn_factors_count);

Другие решения

Других решений пока нет …

Поиск простых чисел разными способами. Сравнение алгоритмов поиска простых чисел по памяти и времени.

Подготовка

Записать php 7 в папку c:php, поместить в эту же папку файл php7.bat со следующим содержимым. Создать папку c:phplocalhost, в неё положить php файлы.

Поиск простых чисел

Перебор простых делителей

Числа проверяются на делимость на простые числа, не превышающие квадратный корень из этого числа. По мере нахождения простых чисел они записываются в массив, который используется для проверки следующих чисел на делимость.

<?
ini_set('max_execution_time',0);

$time=time();

$max=10_000_000;
$primes=array();
$primes[]=2;
$primes[]=3;
$primes[]=5;

for($i=7;$i<$max;$i++)
{
  $sqrt_i=(int)sqrt($i);

  for($j=0;$primes[$j]<=$sqrt_i;$j++)
    if($i%$primes[$j]==0) continue 2;

  $primes[]=$i;
}

echo 'time: ';
echo time()-$time.'<br>';
echo 'memory: '.number_format(memory_get_peak_usage(true)).'<br>';
echo 'primes/all: '.number_format(sizeof($primes));
echo ' / '.number_format($max);

Перебор простых делителей +=2 и 235

Вместо $i++ можно поставить $i+=2. Так будет меньше проверяться. Хотя разницы особой не увидел. Также можно проверять не только лишь все числа, а мало какие можно проверять. По-английски это называется wheel factorization. Колесная факторизация дает еще немного секунд.

//for($i=7;$i<$max;$i++)
for($i=7;$i<$max;$i+=2)

//for($i=7;$i<$max;$i++)
$steps[]=2;
$steps[]=6;
$steps[]=4;
$steps[]=2;
$steps[]=4;
$steps[]=2;
$steps[]=4;
$steps[]=6;
for($i=7,$n=1;$i<$max;$i+=$steps[(++$n)%8])

Решето Эратосфена

Числа 2*2, 2*3, 2*4, …, 3*3, 3*4,… и так далее помечаются как составные. Остальные числа будут простыми. Первый множитель берется как следующее простое число, второй множитель — числа подряд. Википедия.

<?
ini_set('max_execution_time',0);

$max=100_000_000;
$sqrt_max=(int)sqrt($max);

$numbers=str_repeat('1',$max);

$multiplier=2;

$time=time();

while($multiplier<=$sqrt_max)
{
  for($i=$multiplier;$i*$multiplier<$max;$i++)
    $numbers[$i*$multiplier]='0';

  while($numbers[++$multiplier]=='0');
}

echo 'time: ';
echo time()-$time.'<br>';

echo 'memory: ';
echo number_format(memory_get_peak_usage(true)).'<br>';

$primes=0;
for($i=2;$i<strlen($numbers);$i++)
  if($numbers[$i]=='1')$primes++;

echo 'primes/all: '.number_format($primes);
echo ' / '.number_format($max);

Решето Аткина

Описание сложное, можно посмотреть в Википедии.

<?
ini_set('max_execution_time',0);

$max=100_000_000;
$sqrt_max=(int)sqrt($max);

$is_prime=str_repeat('0',$max+1);

$time=time();

$x2=0;
for($i=1;$i<=$sqrt_max;$i++)
{
  $x2+=2*$i-1;
  $y2=0;

  for($j=1;$j<=$sqrt_max;$j++)
  {
    $y2+=2*$j-1;

    $n=4*$x2+$y2;
    if( ($n<=$max) && ($n%12==1 || $n%12==5) )
    {
      if($is_prime[$n]=='0') $is_prime[$n]='1';
      else $is_prime[$n]='0';
    }

    $n-=$x2;
    if( ($n<=$max) && ($n%12==7) )
    {
      if($is_prime[$n]=='0') $is_prime[$n]='1';
      else $is_prime[$n]='0';
    }
    
    $n-=2*$y2;
    if( ($i>$j) && ($n<=$max) && ($n%12==11) )
    {
      if($is_prime[$n]=='0') $is_prime[$n]='1';
      else $is_prime[$n]='0';
    }
  }
}

for($i=5;$i<=$sqrt_max;$i++)
{
  if($is_prime[$i])
  {
    $n=$i*$i;
    for($j=$n;$j<=$max;$j+=$n)
      $is_prime[$j]='0';
  }
}

$primes=3;

for($i=6;$i<$max;$i++)
  if( ($is_prime[$i]=='1') && ($i%3!=0) && ($i%5!=0) )
    $primes++;

echo 'time: ';
echo time()-$time.'<br>';

echo 'memory: ';
echo number_format(memory_get_peak_usage(true)).'<br>';

echo 'primes/all: '.number_format($primes);
echo ' / '.number_format($max);

Решето Сундарама

Решето Сундарама простое, оно пусть будет домашним заданием.

Результаты

Простые/все: 664,579 / 10,000,000

Простые/все: 5,761,455 / 100,000,000

Для сравнения: WinRAR/Меню/Операции/Тест быстродействия, без многопоточности =1200.

Литература

Еще раз о поиске простых чисел