CODEWITHSUNDEEP
phpmathprimes
Ben G
Ben G

Reputation: 26791

What's wrong with my function for finding highest prime factor?

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
    }
}

UPDATE: This is the correct answer, my bad!

Upvotes: 2

Views: 162

Answers (3)

rossum
rossum

Reputation: 15693

Starting at 2 and stepping by 1 is inefficient. At least check 2 separately and then loop from 3 stepping 2 each time. Using a 2-4 wheel would be even faster.

When you recurse your code starts again at trial factor 2. It would be better to pass a second parameter holding the factor you have reached so far. Then the recursion wouldn't have go back over old factors that have already been tested.

Upvotes: 0

Bob Vale
Bob Vale

Reputation: 18474

Get rid of the final if statement otherwise if $i!=sqrt($n) because sqrt($n) is not an integer you have an undefined return value 

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
 }

Upvotes: 2

Jonah
Jonah

Reputation: 16232

Line 11 should be:

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

Upvotes: 1

Related Questions