Finde den Primfaktor für eine bestimmte Zahl - PHP, Algorithmus, Faktoren

Was stimmt nicht mit dem Code, den ich geschrieben habe? Ich versuche, eine Frage im Euler-Projekt zu lösen.

Danke dir :)

Ich fügte Anführungszeichen zum Code hinzu, damit Sie alles, was ich getan habe, verstehen können. Es funktioniert für die Nummer 13915, aber nicht für die Nummer, die ich brauche.

Das Problem ist, dass bei der Überprüfung die Zahl in 3 geteilt wird, und obwohl es keine vollständige Zahl ist, sagt es immer noch, dass es eine Primzahl ist.

beispielsweise:

3 ist ein Primfaktor von 600851475143

neue nummer: 200283825047.67

neue größte Primzahl: 3

 <?php
/**
* Created by PhpStorm.
* User: gabia_000
* Date: 13/08/2015
* Time: 23:32
*
* Project euler - Question 3 ;
* The prime factors of 13195 are 5, 7, 13 and 29.
* What is the largest prime factor of the number 600851475143 ? ;
*/

$num = 600851475143; // The number that contains the factors ;
$largest = 1; // the largest prime factor ;
$n = 3; // the count of number starting 3 to find the prime factor ;
echo "<b>number - ".$num."</b><br /><br />"; // DISPLAY ;
while ($num > 1) { // as long as the number isnt 1 yet ;
$prime = 1; // defult true - the $n is prime;
$i = 2; // number that the prime is divide by ;
while($i < $n && $prime == 1) { // as long as $n is bigger then $i and prime is still true ;
if($n % $i == 0) { // if $n is divided in $i ;
$prime = 0; // prime false ;
echo "{$n} not a prime, divided by {$i}.<br />"; // DISPLAY ;
break 1; // break the while ;
}
$i = $i + 1; // increase the $i by 1 ;
}
if ($prime) { // if the prime is still true ;
if($num % $n == 0) { // if the prime number is a factor of the number ;

echo "{$n} is a prime factor of {$num}<br />"; // DISPLAY ;
$num = $num / $n; // set the new number ;
echo " - new number: {$num}<br />"; // DISPLAY ;
$largest = $n; // set the new largest prime factor ;
echo " - new largest prime: {$largest}<br />"; // DISPLAY ;

}
else { // if the prime number isnt a factor of the number ;
echo "{$n} is not a prime factor of {$num}<br />"; // DISPLAY ;
}
}
$n = $n + 1; // increase the $n by 1 ;
if($n > $num) { // if the $n is bigger then the number is there is no prime factor ;
break ; // break the while ;
echo "<br /><br /><b>no prime factors for </b>{$num}}"; // DISPLAY ;
}
}
// DISPLAY END RESULTS ;
echo "
latest $n - <b>{$n}</b><br />
largest prime - <b>{$largest}</b><br />
number - {$num}
";

Antworten:

Sie müssen nicht jeden Schritt auf Ursprünglichkeit überprüfen. Vielleicht einfacher:

<?php
/**
* Created by PhpStorm.
* User: gabia_000
* Date: 13/08/2015
* Time: 23:32
*
* Project euler - Question 3 ;
* The prime factors of 13195 are 5, 7, 13 and 29.
* What is the largest prime factor of the number 600851475143 ? ;
*/

$num = 600851475143; // The number that contains the factors ;
$num_save = $num;
$largest = 1; // the largest prime factor ;
$n = 2; // the count of number starting 3 to find the prime factor ;
echo "<b>number - ".$num."</b><br /><br />"; // DISPLAY ;


while ($num > 1) { // as long as the number isnt 1 yet ;

if($num % $n == 0) {
$largest = $n;

while($num % $n == 0) {
$num = $num / $n;
}
}
$n = $n + 1;
}
echo "
latest $n - <b>{$n}</b><br />
largest prime - <b>{$largest}</b><br />
number - {$num_save}
";

?>