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

Вот небольшая функция, которую я нашел: ( 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; } 

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

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

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

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

 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 

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

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

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

Все, что является sqrt (), является ложным или любое значение float является простым числом

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

Он проверяет каждое число ($ x), чтобы узнать, есть ли у него какие-либо факторы (кроме него и 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>"; } 

 <?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/

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

  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);

 $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'; } 

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; } не 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; } 

Найдите простые числа от 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); 

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

Лучший способ проверить, является ли число простым, – это увидеть, делится ли он каким-либо простым числом перед ним. 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 ) ); } } 

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

Использование вышеуказанного было бы следующим образом:

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

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

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

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

 <?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 eg 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++; } ?> 

 <?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); ?> 

Исправлена ​​версия ответа @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; } 

Тест с phpfiddle.org. V1 – ответ Farkie, V2 – расширенная версия

 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 будет иметь недостаточную историю.

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

 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); с 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);