php - 找到特定数字的质因数

Question

我写的代码有什么问题？ 我正在尝试解决 euler 项目中的一个问题。

谢谢你:)

我在代码中添加了引号，这样您就可以理解我所做的一切。它适用于号码 13915，但不适用于我需要的号码。

问题是我检查数字被分成 3，虽然它不是一个完整的数字，但它仍然说它是一个质数。

例如:

3 is a prime factor of 600851475143

new number: 200283825047.67

new largest prime: 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}
    ";

Answer 1

您不必检查每一步的素性。 也许更简单:

<?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}
    ";

?>