Список чисел, пока n не делится на A или B, но не делится на C

Question

У меня есть три целых числа: A, B, C

Я хочу напечатать все целые числа от 1 до диапазона, которые делятся на A или B, но не на C.

Мой код

for($n=0; $n < $range; $n++){
   if(($n < $a && $n < $b) || ($n % $c == 0)){
     return [];
   }
   if(($n % $a == 0 || $n % $b == 0) && ($n % $c > 0)){
     $outputArr[] = $n; 
   }
}

Есть ли более эффективный способ сделать это?

Answer 1

PHP версии 7 или выше работает так быстро, когда используются только целочисленные операции, поэтому микрооптимизации больше не нужны.

$res = [];
$a = 9;
$b = 13;
$c = 26;
$range = 10000;

for($n=$a; $n <= $range; $n += $a){
  if($n%$c != 0) $res[] = $n;
}
for($n=$b; $n <= $range; $n += $b){
  if($n%$c != 0) $res[] = $n;
}

$res = array_unique($res);
sort($res);

В этом примере требуется около 1 миллисекунды для вычисления 1411 значений на моих 8-летняя система. На этот раз для представления результата в несколько раз больше.

Answer 2

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

Сначала напишите функцию наибольшего общего делителя (gcd) в PHP, а затем напишите наименее общее кратное (lcm) функция , использующая функцию gcd. Вычислите m = lcm (a, b). Выполните итерацию по кратным из a и распечатайте их, если они не делятся на c. Затем выполните итерацию по кратным числам b и распечатайте их, если они не делятся на m или c.

Возможны другие оптимизации в этом направлении. Например, вы можете предварительно вычислить кратные a или b, которые не являются кратными m, и сохранить их в массиве. Это работает, если m не слишком велико, деление обходится дороже, чем доступ к массиву в PHP, а диапазон значительно больше, чем m.

Answer 3

Я бы использовал range() и array_filter().

$range = 20;
$A = 2;
$B = 3;
$C = 9;

$nums = array_filter(range(1, $range), function ($x) use ($A, $B, $C) {
    return (!($x % $A) || !($x % $B)) && $x % $C;
});

var_dump($nums);

Answer 4

Вот более оптимизированное решение, которое также эффективно работает при больших a и b. Вы можете просто набрать кратные значения a и b:

for($na=$a, $nb=$b; $na <= $range || $nb <= $range;  ){
   if ($na <= $nb) {
      if ($na % $c != 0)
         $outputArr[] = $na; 
      if ($na == $nb)
         $nb += $b;
      $na += $a;
   } else {
      if ($nb % $c != 0)
         $outputArr[] = $nb; 
      $nb += $b;
   }
}

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

Если вы боитесьтест по модулю медленный, вы также можете запустить next multiple of c, но это выглядит слишком много.