在循环中查找素数的公式
我需要findfor循环或while循环的素数
我写了这个，但这是错误的
<?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; } ?> 有没有办法用数组分割一个数字来find剩下的数字？
这里有一个小function，我发现：（ 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()
这里是我发现一段时间后检查质数的一行。 它使用标记（一元math）来确定：
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
完整的逻辑在这里一步一步的和可视化的比喻： 在这里
没有mathfunction：
function isPrimeNumber($i) { $n = 2; while ($n < $i) { if ($i % $n) { $n++; continue; } return false; } return true; }
任何sqrt（）是false的，或者任何float值都是素数
我相信这是一个非常有效的例程，它列出了所有达到1000的素数。
它testing每个数字（$ x），以查看它是否有任何因素（当然除外，当然是1）。
在math上，没有必要testing所有较低的数字作为可能的因素，只有更低的素数直到$ x的平方根。 这是通过存储素数，因为它们是在一个数组中find（我认为这是OP所指的策略）。
只要find第一个素因子，我们知道$ x不是素数，所以不需要进一步testing$ 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; } } ?>
我知道这是晚了，但希望它可以帮助别人。
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是简单和快速的algorithm来find素数。
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; }
使用array_filter（）中的闭包查找1到10000之间的素数：
$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的更多信息。
所以我现在想到的最有效的方法是：
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 ) ); } }
实际上，这并不是非常有效的，当然，并不是build立素数列表时，我一直在寻找一个更好的方式来build立这个列表，虽然它会一样简单，效率也更高在网上find一个列表并使用它。
上述的使用将沿着以下方向进行：
$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"; }
我知道这个太晚了，但是我发现这个解决scheme更好更容易
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的encryption版本特别适用于检查循环中的素数。
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数组将具有不足的历史logging。
这是另一个非常简单但安静的有效方法：
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);
