Что не так с моей функцией нахождения наивысшего простого множителя?

Question

function find_highest_prime_factor($n)
{
    for ($i = 2; $i <= $n; $i++) 
    {   
        if (bcmod($n, $i) == 0) //its a factor
        {
            return max($i, find_highest_prime_factor(bcdiv($n,$i)));
        }
    }
    if ($i == $n)
    {
        return $n; //it's prime if it made it through that loop
    }
}

ОБНОВЛЕНИЕ : Это правильный ответ, мой плохой!

Answer 1

Избавиться от последнего оператора if, в противном случае, если $i!=sqrt($n), потому что sqrt ($ n) не является целым числом, у вас есть неопределенное возвращаемое значение

function find_highest_prime_factor($n){
  for ($i = 2; $i <= sqrt($n); $i++) //sqrt(n) is the upperbound
  {
       if (bcmod($n, $i) == 0) //its a factor
       {
          return max($i, find_highest_prime_factor(bcdiv($n,$i)));
       }
   }
   return $n; //it's prime if it made it through that loop
 }

Answer 2

Строка 11 должна быть:

if ($i == ceil(sqrt($n)))

Answer 3

Начиная с 2 и переходя на 1 неэффективно. По крайней мере, отметьте 2 отдельно, а затем повторите цикл из 3 степеней 2 каждый раз. Использование колеса 2-4 будет еще быстрее.

Когда вы повторяете код, ваш код запускается снова с пробным коэффициентом 2. Было бы лучше передать второй параметр, содержащий коэффициент, которого вы достигли до сих пор. Тогда рекурсия не вернулась бы к старым факторам, которые уже были проверены.