php - PHPで範囲内の素因数を見つける方法

Question

素因数を求めるプログラムです。

同様に - 数 1125 の素因数は3、5

私のアルゴリズムはうまくいきます-（正しくない場合はお知らせください）

1. まず、関数を使用して数値の平方根を見つけてsqrt() 、複雑さと実行時間を解消しています。
2. 範囲内の素数を見つける。
3. 最後に、これらの素数を元の数で割ります (ただし、2 番目のステップで失敗したため、このステップには到達していません。

私のコードが機能していません。ステップ 2 とステップ 3 のロジックとコードの正確な場所を教えてください。

エラーはスローされませんが、コードも何も出力していません。

<?php
error_reporting(E_ALL);
$number = 6006;

$sqrt_num = (int)sqrt($number);

for($i=2;$i<$sqrt_num;$i++)
{
    for($j=2;$j<=$i-1;$j++)
    {
        if($i%$j==0)
        break;
        if($i==$j) 
            echo $i;
    }   
}

Answer 1

数値の素因数、または 1 から sqrt(number) までの範囲内のすべての素数が必要かどうかは確かなので、しばらく前に書いたコードの一部を示し、さまざまな実装を示します。

//Check if a number is prime
function isPrime($num, $pf = null)
{
    if(!is_array($pf)) 
    {
        for($i=2;$i<intval(sqrt($num));$i++) {
            if($num % $i==0) {
                return false;
            }
        }
        return true;
    } else {
        $pfCount = count($pf);
        for($i=0;$i<$pfCount;$i++) {
            if($num % $pf[$i] == 0) {
                return false;
            }
        }
        return true;
    }
}

//Find Prime Factors
function primeFactors($num)
{
    //Record the base
    $base = intval($num/2);
    $pf = array();
    $pn = null;
    for($i=2;$i <= $base;$i++) {
        if(isPrime($i, $pn)) {
            $pn[] = $i;
            while($num % $i == 0)
            {
                $pf[] = $i;
                $num = $num/$i;
            }
        }
    }
    return $pf;
}

そこから、素因数を取得するには、次を使用します$myarr = primeFactors($number);(そして、独自の再作成に使用されるロジックを確認できます。^^)

範囲内のすべての素数が必要な場合:

for($i=1;$i<$sqrt_num;$i++) {
    if(isPrime($i)) {
        $myarr[] = $i;
    }
}

$pfinの使用に注意したいのisPrimeは、既に処理された素因数に基づいて数値が素数であるかどうかを調べる処理時間を短縮するふるいであるためです。

Answer 2

素数を見つけることは、ほとんどのプログラミング言語で共通の問題です。まず、number is primeを見てください。機能を使用できますgmp_nextprime。

Answer 3

PrimeModuleでphpクラスを使用できます

膨大な数の素因数分解を非常に迅速に実行できる PHP Prime モジュール。

リンク: https://github.com/danog/PrimeModule

Answer 4

$namber = 1122676330;
$text = $namber.'=';
$time_start = microtime(1);

for($i=2; $i<=$namber; $i++ ){
    if($namber % $i == 0){
        $namber = $namber / $i;
        $text .= $i. '  ';
        $i--;
    }
    if($namber == 1){
            echo 'ok';
        }
}

$time_end = microtime(1);
$time = $time_end - $time_start;
echo "<br><br>$text<br><br> $time seconds\n";