формулы для поиска простых чисел в цикле

Question

мне нужно найти простые числа с для цикла или во время цикла

Я написал это, но это неправильно

<?php 
$i = 1; 
while($i<5) 
{ 
    for($j=1; $j<=$i; $j++) 
    { 
     if ($j != 1 && $j != $i) 
     { 
      echo $i . "/" . $j . "=" . $i%$j . "<br />"; 
      if ($i%$j != 0) 
      { 
       echo $i . "<br />"; 
      } 
     } 
    } 
    echo "<br />"; 
    $i += 1; 
} 
?> 

Есть ли способ разделить число с массивом, чтобы найти оставшиеся?

Answer 1

Вот небольшая функция, которую я нашел: (http://icdif.com/computing/2011/09/15/check-number-prime-number/) Показалось работать для меня!

function isPrime($num) { 
    //1 is not prime. See: http://en.wikipedia.org/wiki/Prime_number#Primality_of_one 
    if($num == 1) 
     return false; 

    //2 is prime (the only even number that is prime) 
    if($num == 2) 
     return true; 

    /** 
    * if the number is divisible by two, then it's not prime and it's no longer 
    * needed to check other even numbers 
    */ 
    if($num % 2 == 0) { 
     return false; 
    } 

    /** 
    * Checks the odd numbers. If any of them is a factor, then it returns false. 
    * The sqrt can be an aproximation, hence just for the sake of 
    * security, one rounds it to the next highest integer value. 
    */ 
    $ceil = ceil(sqrt($num)); 
    for($i = 3; $i <= $ceil; $i = $i + 2) { 
     if($num % $i == 0) 
      return false; 
    } 

    return true; 
} 

Answer 2

Вы можете использовать эту функцию PHP gmp_nextprime()

Answer 3

Это, я считаю, является весьма эффективной рутиной, в котором перечислены все простые числа до 1000.

Он проверяет каждое число ($ х), чтобы увидеть, если он имеет какие-либо факторы (другая чем само и 1, конечно).

Математически нет необходимости проверять все нижние числа как возможные факторы, только нижние простые числа до квадратного корня от $ x. Это активируется путем хранения простых чисел, поскольку они находятся в массиве (который, я думаю, является стратегией, о которой ссылался OP).

Как только первый простой коэффициент найден, мы знаем, что $ x не является простым, и поэтому дальнейшее тестирование этого значения $ x не требуется, и мы можем выйти из цикла foreach.

$primes = array(); 
for ($x = 2; $x <= 1000; $x++) { 
    $xIsPrime = TRUE; 
    $sqrtX = sqrt($x); 
    foreach ($primes as $prime) if ($prime > $sqrtX || ((!($x % $prime)) && (!$xIsPrime = FALSE))) break; 
    if ($xIsPrime) echo ($primes[] = $x) . "<br>"; 
} 

Answer 4

Это базовая реализация:

function prima($n){ 

    for($i=1;$i<=$n;$i++){ //numbers to be checked as prime 

      $counter = 0; 
      for($j=1;$j<=$i;$j++){ //all divisible factors 


       if($i % $j==0){ 

         $counter++; 
       } 
      } 

     //prime requires 2 rules (divisible by 1 and divisible by itself) 
     if($counter==2){ 

       print $i." is Prime <br/>"; 
     } 
    } 
} 

prima(20); //find prime numbers from 1-20 

Это выведет

2 is Prime 
3 is Prime 
5 is Prime 
7 is Prime 
11 is Prime 
13 is Prime 
17 is Prime 
19 is Prime 

Полная логика шаг за шагом и визуальной аналогии здесь: Here

Answer 5

я знаю, что это наступая поздно, но надеюсь, что это поможет кому-то.

function prime_number_finder($range) 
    { 
     $total_count=0;//intitialize the range keeper 

     $i=1;//initialize the numbers to check 

     while ($total_count<=$range) 
     { 
      $count=0;//initialize prime number inner count 
      $k=$i; 
      while ($k!=0) 
      { 

      if(($i%$k)==0) 
      { 
       $count++; 
      } 
       $k--; 
      } 
      //condition to check if a number is prime 
      if($count==2 || $count==1) 
      { 
      echo $i."</br>";//output the prime number; 
      $total_count++; 
      $i++; 

      } 
      //number is not prime 
      if($count>2) 
      { 
      //$total_count++; 
      $i++; 
      } 

     } 
    } 

// Пример prime_number_finder (200);

Answer 6

Все, кто SQRT() является ложным или любым значением с плавающей точкой является простым числом

Answer 7

Вот один вкладыш, я нашел некоторое время назад, чтобы проверить простые числа. Он использует учетные знаки (унарная математику), чтобы определить:

function is_prime_via_preg_expanded($number) { 
    return !preg_match('/^1?$|^(11+?)\1+$/x', str_repeat('1', $number)); 
} 

Проверить все номера последовательно для простых чисел:

$i=2; // start here (2 is the first prime) 
while (1) { // neverending loop 
    if (is_prime_via_preg_expanded($i)) echo $i." <br />\n"; 
    $i++; 
} 

Чтобы проверить только диапазон номеров для простых чисел, как в указанном примере:

$start = 2; // start here (2 is the first prime) 
$end = 100; 

$i=$start; 
while ($i<=$end) { 
    if (is_prime_via_preg_expanded($i)) echo $i." <br />\n"; 
    $i++; 
} 

Answer 8

$n = 7; 

if ($n == 1) { 
    echo 'Not a Prime or Composite No.'; 
} 

$set = 0; 
for ($index = 2; $index <= $n/2; $index++) { 

    if ($n % $index === 0) { 
     $set = 1; 
     break; 
    } 
} 

if ($set) { 
    echo 'Composite'; 
} else { 
    echo 'Prime'; 
} 

Answer 9

Sieve_of_Eratosthenes - простой и быстрый алгоритм для нахождения простых чисел.

function getPrimes($finish) 
    { 
     $number = 2; 
     $range = range($number,$finish); 
     $primes = array_combine($range,$range); 
     while($number*$number < $finish){ 
      for($i=$number; $i<=$finish; $i+=$number){ 
       if($i==$number){ 
        continue; 
       } 
       unset($primes[$i]); 
      } 
      $number = next($primes); 
     } 
     return $primes; 
    } 

Answer 10

Без математической функции:

function isPrimeNumber($i) { 
    $n = 2; 
    while ($n < $i) { 
     if ($i % $n) { 
      $n++; 
      continue; 
     } 

     return false; 
    } 

    return true; 
} 

Answer 11

Найти простые числа в диапазоне от 1 до 10000, используя замыкание в array_filter():

$start = 2; 
$step = 10000; 

$stop = $start + $step; 
$candidates = range($start, $stop);  
for($num = 2; $num <= sqrt($stop); ++$num){       
    $candidates = array_filter($candidates, 
     function ($v) use (&$num){ 
      return ($v % $num) != 0 || $v == $num ; 
     } 
    ); 
} 
print_r($candidates); 

Edit: 1 не является простым числом

Answer 12

Лучший способ проверить, является ли число простым, - это увидеть, если он делится на любое простое число перед ним. Pi (x) - это тот, который я вижу повсюду ... Вы можете увидеть немного больше информации о Prime Counting on wikipedia.

Таким образом, наиболее эффективным способом я могу думать на данный момент выглядит следующим образом:

class prime 
{ 
    public $primes = [ 2, 3, 5, 7 ]; 
    public $not_prime = [ 1, 4, 6, 8, 9 ]; 
    public function is_prime(int $n) 
    { 
     if ($n <= 1) return false; 
     if (in_array($n, $this->primes)) return true; 
     if (in_array($n, $this->not_prime)) return false; 
     for($i = 0; $i < count(array_slice($this->primes, 0, $this->prime_count($n))) || $i == $n; $i++) 
     { 
      if ($n % $this->primes[ $i ] == 0) return false; 
     } 
     return true; 
    } 
    public function build_primes_to(int $n) 
    { 
     for ($i = end($this->primes) + 1; $i <= $n; $i++) 
     { 
      if ($this->is_prime($i)) 
      { 
       $this->primes[] = $i; 
      } 
      else 
      { 
       $this->not_prime[] = $i; 
      } 
     } 
    } 
    public function prime_count($n) 
    { 
     $ln = log($n); 
     if ($ln == 0) return 1; 
     return intval(ceil($n/$ln)); 
    } 
} 

Что на самом деле не очень эффективным, а не тогда, когда речь идет о создании списка простых чисел .. Я работал над лучшим способом построения списка here, хотя было бы легко и гораздо эффективнее найти список в Интернете и использовать его.

Использование выше будет вдоль линий:

$find_to = 1000; 
$prime = new prime(); 
$prime->build_primes_to($find_to); 
print "<pre>"; 
for ($i = 1; $i < $find_to; $i++) 
{ 
    print "$i is " . (!$prime->is_prime($i) ? "not " : "") . "prime\n"; 
} 

Answer 13

Я знаю, это слишком поздно, но я обнаружил, что это решение гораздо лучше и легко

function isPrime($num) 
{ 
    if ($num < 2) { 
     return false; 
    } 
    for ($i = 2; $i <= $num/2; $i++) { 
     if ($num % $i == 0) { 
      return false; 
     } 
    } 

    return true; 
} 

Answer 14

<?php 

    $n = 11; 
    $o = $_POST["maxprime"]; 
    echo 'The script calculated the next primenumbers:</br>'; 
    echo '2, 3, 5, 7, '; 
    while (true) { 
     $t = 6; 
     while (true) { 
      if ($n % ($t - 1) == 0) { 
       break; 
      } 
      if ($n % ($t + 1) == 0) { 
       break; 
      } 
      if ($t > sqrt($n)) { 
       echo("$n, "); 
       break; 
      } 
      $t += 6; 
     } 
     if (($n + 1) % 6 == 0) { 
      $n += 2; 
     } else { 
      $n += 4; 
     } 
     if ($n > $o) { 
      break; 
     } 
    } 

?> 

http://www.primenumbergenerator.com/

Answer 15

Я знаю, что это придет немного поздно, но вот простая программа, которая поможет вам сделать то, что вы просить ...

<?php 
//Prime Function 
function fn_prime($number) { 
    $i = 2; $result = TRUE; 
    while($i < $number) { 
     if(!($number%$i)) { 
      $result = FALSE; 
     } 
     $i++; 
    } 
    return $result; 
} 

//Declare integer variable... 
$k = 0; 

//Start Loop up to any number of your choice for e.g. 200 
while($k < 200) { 
    if(fn_prime($k)) { 
     echo "$k is a prime number<br/>"; 
    } else { 
     echo "$k is not a prime number!<br/>"; 
    } 
    $k++; 
} 

?> 

Answer 16

<?php 
function prime_number($num){ 
    for($j = 2; $j <= $num; $j++) 
    { 
     for($k = 2; $k < $j; $k++) 
     { 
      if($j % $k == 0) 
      { 
       break; 
      } 
     } 
     if($k == $j) 
      echo "Prime Number : ".$j."<br>"; 
    } 
} 
prime_number(23); 
?> 

Answer 17

Enchanced версии @Farkie ответ сделал специально для проверки простых чисел в петлях.

function isPrime_v2($num) { 
    static $knownPrimes=[3]; // array to save known primes 

    if($num == 1) 
     return false; 

    if($num == 2 || $num == 3) //added '3' 
     return true; 

    if($num % 2 == 0) 
     return false; 

    $ceil = ceil(sqrt($num)); //same purpose, good point from Farkie 

    // Check against known primes to shorten operations 
    // There is no sense to check agains numbers in between 
    foreach($knownPrimesas $prime){ 
     if ($prime>$ceil) 
      break; 
     if($num===$prime) 
      return true; 
     if($num % $prime == 0) 
      return false; 
    } 


    /** 
    * end($knownPrimes) % 2 !==0 - mathematically guaranteed 
    * start with latest known prime 
    */ 
    for($i = end($knownPrimes)+2; $i <= $ceil; $i = $i + 2) { 
     if($num % $i == 0) 
      return false; 
    } 
    $knownPrimes[]=$num; 
    return true; 
} 

Benchmark с phpfiddle.org. V1 - Farkie ответ, V2 - Enchanced версия

V1 (1 to 5,000,000): divisions=330 929 171; primes=348 513; time=21.243s 
V2 (1 to 5,000,000): divisions=114 291 299; primes=348 513; time=10.357s 

ВНИМАНИЕ!isPrime_v2 функция применима ТОЛЬКО в случае петли с 3. В противном случае сохраненный массив $ knownPrimes будет иметь недостаточную историю.

Answer 18

Вот еще один очень простой, но тихий эффективный подход:

function primes($n){ 

    $prime = range(2 , $n); 

    foreach ($prime as $key => $value) { 

     for ($i=2; $i < $value ; $i++) { 

      if (is_int($value/$i)) { 

       unset($prime[$key]); 
       break; 
      } 
     } 
    } 

    foreach ($prime as $value) { 
     echo $value.'<br>'; 
    } 
} 

primes(1000);