Как найти простые множители в диапазоне в php

Question

Это программа для поиска простых коэффициентов чисел.

Как - Prime факторы для числа 1125 являются 3 и 5

Мой Algo это идет путь - (и, пожалуйста, дайте мне знать, если это не правильно)

1. Во-первых, я найти квадратный корень от числа, использующего функцию sqrt() , чтобы разрушить сложность и время выполнения.
2. Чтобы найти простые числа между диапазонами.
3. Наконец, чтобы разделить эти простые числа с оригинальным номером (еще не дошел до этой стадии, как неудача на втором этапе.

Моего код, который не работает, дайте мне знать, где именно я терплю неудачу в моем логика и код, начиная с шага 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

Нахождение простых чисел является общей проблемой в м ost языки программирования. Сначала взгляните на number is prime. Вы можете использовать функцию gmp_nextprime.

Answer 2

Поскольку я уверен, что если вам нужны простые коэффициенты числа или все простые числа в диапазоне от 1 до sqrt (число), я дам вам часть моего кода, который я написал некоторое время назад, показать различные варианты реализации: (., и вы можете увидеть логику, используемую для воссоздания собственного ^^)

//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; 
    } 
} 

Я хочу отметить использование $pf в isPrime, так как это сито, чтобы сократить время обработки, чтобы узнать, является ли число простым на основе уже обработанных основных факторов.

Answer 3

$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"; 

Answer 4

вы можете использовать класс PHP на PrimeModule

PHP премьер модуль, способный делать простые множители огромных чисел очень быстро.

ссылка: https://github.com/danog/PrimeModule