Factorising Primes

[HFD]

Hi, I've currently written a prime test algorithm, and I want to extend it to factorise numbers into primes. For example, 55 factorises into 5 and 11.

 

Here's part of the code I have so far for the prime testing - how would I extend this to factorise into primes? Thanks

 

for ($check = 2; $check <= sqrt($num); $check++){
        if ($num % $check == 0){
            echo "This number is not prime. because $check is a factor! <a href=\"prime.php\">Try another number?</a>";
            die();
            }
        }
        
        echo "Number is prime! <a href=\"prime.php\">Try another number?</a>";
        die();       

[soak]

<?php
$factors = array();
for ($check = 2; $check <= sqrt($num); $check++){
        if ($num % $check == 0){
            echo "This number is not prime. because $check is a factor! <a href=\"prime.php\">Try another number?</a>";
            die();
            }
        }
        else {
            $factors[] = $check;
        }
       
        echo "Number is prime! <a href=\"prime.php\">Try another number?</a>";
        echo "Factors are: ".implode(', ', $factors);
        die();       

[jackpf]

Just wondering about that last bit of code - how can the number be prime and have factors? I think there's some flaw in your logic there.

 

Try this:

<?php
$num = 12;
$p = array();
$p2 = array();
for ($check = 2; $check <= sqrt($num); $check++){
       if($num % $check == 0)
	{
		$p[] = $check;
		$p2[] = $num / $check;
	}
	else
	{
		//die('prime');
	}
}

      foreach($p as $key => $value)
   {
	echo $value.' and '.$p2[$key].'<br />';
   }
?>

[jackpf]

Whoah, not sure what's going on with them dodgy hexadecimal symbols, I didn't put them there. SMF's fault.

[soak]

LOL :slap:

 

Technically my code should work though ;-p If there are any factors in those primes it'll definitely find them!

[jackpf]

<?php
$num = 5;
$p = array();
$p2 = array();
for($check = 2; $check <= sqrt($num); $check++)
{
	if($num % $check == 0)
	{
		$p[] = $check;
		$p2[] = $num / $check;
	}
}
if(count($p) == 0)
{
	echo 'This number is prime.';
}
else
{
	foreach($p as $key => $value)
	{
		echo $value.' and '.$p2[$key].'<br />';
	}
}
?>

 

Revisions! This works perfectly. I'm pretty proud of myself

[HFD]

Thanks for both your help guys only thing is I'm having a bit of trouble - I understand the code you guys posted and it works, but not in the way I intend it too. I'm given this example, which the program should do:

 

520 should factorize 2 × 2 × 2 × 5 × 13

 

Something like this I think : http://www.btinternet.com/~se16/js/factor.htm

 

Thanks again

[soak]

<?php
  function factorise($numm)                      // To calculate the prime factors of a number
     {
      $newnum = $numm;                        // Initialise
      $newtext = "";
      $checker = 2;                          // First possible factor to check

      while ($checker*$checker <= $newnum)         // See if it is worth looking further for factors 
         {      
          if ($newnum % $checker == 0)            // If the possible factor is indeed a factor...
             { 
              $newtext = $newtext . $checker;      // ...then record the factor
              $newnum = $newnum/$checker;          //    and divide by it
              if ($newnum != 1)                  //    then check whether it is not last...
                 {
                  $newtext = $newtext . ".";      //    ...and if so prepare for the next
                 }
             }
          else                                  // otherwise...
             {
              $checker++;                        // try the next possible factor
             }
         }
      if ($newnum != 1)                          // If there is anything left at the end...
         {                                      // ...this must be the last prime factor
          $newtext = $newtext . $newnum;           //    so it too should be recorded
         }
      if ($newtext == "" . $numm)                 // If the only prime factor is the original...
         {
          $newtext = "Prime: " . $newtext;        // ...then note that it must have been prime.
         }

      return $newtext;                           // Return the prime factors
     }

 

[jackpf]

Works quite well actually. Well done.

 

Yeah, I just realised my code doesn't actually return primes, but any factors.

Ahh well.

[soak]

The  was because I copy and pasted the javascript from the linked page and added a few $ signs to it ;-)

[jackpf]

Lol cheeky.

[Daniel0]

It's not perfect though...

 

echo factorise(68168712496431); => 83.353.755.1076.2864.000377144

 

The three last ones are clearly not prime numbers.

[Mchl]

Last four of them.

The input is above 2^32, so BC Math extension could help here.

[HFD]

Thanks for your replies

 

I've currently been adapting the code to work with my current prime algorithm, just to stay consistent - I have the following

 

<?php
$num = $_POST['number'];
    $factors = array();
    $i = 0;

    if ($num > 0 && $num < 10000)   
    {
    
           for ($check = 2; $check <= sqrt($num); $check++){
            if ($num % $check == 0){
	$factors[$i] = $check;
	$num = $num / $check;
	$i++;             
            }

        }
        
if (count($factors) == 0)
{
	echo "Number is prime";
} else {
	echo "Number is not prime! Factors are listed below";
	for ($counter = 0; $counter < $factors[$counter]; $counter++)
	{
		echo "$factors[$counter] x ";
	}
}

} else {
    echo "Number is not between 0 and 9999!";
    }
?>

 

But it doesn't work correctly...rather than factorising as 2 * 2 * 2 * 5 * 13 as it should, it just comes out as 2 * 4 * 5...sorry to be a pain with this, maths is not my strong point 

 

[corbin]

Elements of the $factors[$i] array are not guarenteed to be prime, so you will have to 'factorize' those too.

 

 

(4 expands to 2 * 2)