0

This is a program to find prime factors of a numbers.

Like - Prime factors for number 1125 are 3 and 5

My Algo this goes way - (and please let me know if it is not correct)

  1. Firstly I am finding a square root of the number using sqrt() function to break the complexity and run time.
  2. To find prime numbers in between the range.
  3. Lastly to divide these prime numbers with the original number(yet not reached to this step as failing in the second step.

My code which is not working, let me know where exactly I am failing in my logic and code from step 2 and step 3.

No error thrown but the code is also not outputting anything.

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

4 回答 4

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，因为它是一种筛子，可以减少根据已处理的素数因子找出一个数是否为素数的处理时间。

于 2013-02-24T13:15:02.923 回答
0

查找素数是大多数编程语言中的常见问题。首先，看一下number is prime。您可以使用该gmp_nextprime功能。

于 2013-02-24T12:19:32.990 回答
0 
$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";
于 2017-02-10T20:19:03.920 回答
0

您可以在PrimeModule上使用 php 类

PHP Prime 模块能够非常快速地对大量数字进行素数分解。

链接： https ://github.com/danog/PrimeModule

于 2017-12-10T20:29:20.940 回答