php 在循环中查找素数的公式
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/16763322/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
A formula to find prime numbers in a loop
提问by Mohammad Masoudian
I need to find prime numbers with for loop or while loop
我需要使用 for 循环或 while 循环查找素数
I wrote this but this is wrong
我写了这个，但这是错误的
<?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;
}
?>
Is there a way to divide a number with an array to find the remaining?
有没有办法用数组除以一个数字来找到剩余的数字？
回答by Farkie
Here's a little function that I found: (http://icdif.com/computing/2011/09/15/check-number-prime-number/) Seemed to work for me!
这是我发现的一个小功能：（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;
}
回答by happy
You can use this PHP function gmp_nextprime()
你可以使用这个 PHP 函数 gmp_nextprime()
回答by Jeff Clayton
Here is a one-liner I found a while back to check for primes. It uses tally marks (unary math) to determine:
这是我不久前找到的一个单线来检查素数。它使用计数标记（一元数学）来确定：
function is_prime_via_preg_expanded($number) {
return !preg_match('/^1?$|^(11+?)+$/x', str_repeat('1', $number));
}
Check all numbers sequentially for primes:
依次检查所有数字的素数：
$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++;
}
To check only a range of numbers for primes like in the provided example:
仅检查一系列数字的质数，如提供的示例中所示：
$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++;
}
回答by ngakak
This a basic implementation :
这是一个基本的实现：
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
This will output
这将输出
2 is Prime
3 is Prime
5 is Prime
7 is Prime
11 is Prime
13 is Prime
17 is Prime
19 is Prime
Complete Logic step-by-step and visual analogy here : Here
完整的逻辑分步和视觉类比在这里： 这里
回答by ghaliano
Without math function:
没有数学函数：
function isPrimeNumber($i) {
$n = 2;
while ($n < $i) {
if ($i % $n) {
$n++;
continue;
}
return false;
}
return true;
}
回答by Nik Latkin
I know it is too late, but I found that this solution is more elegant.
我知道为时已晚，但我发现这个解决方案更优雅。
function isPrime($num)
{
if ($num < 2) {
return false;
}
for ($i = 2; $i <= $num / 2; $i++) {
if ($num % $i == 0) {
return false;
}
}
return true;
}
回答by Nikba
Anything who's sqrt() is false or any float value is prime number
任何 sqrt() 为 false 或任何浮点值都是素数
回答by mocak
Sieve_of_Eratosthenesis simple and faster algorithm to find prime numbers.
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;
}
回答by mocak
<?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;
}
}
?>
回答by WebSmithery
This, I believe, is a quite efficient routine, which lists all the primes up to 1000.
我相信，这是一个非常有效的例程，它列出了 1000 以内的所有素数。
It tests each number ($x) in order to see if it has any factors (other than itself and 1, of course).
它测试每个数字 ($x) 以查看它是否有任何因子（当然，除了它自己和 1）。
Mathematically it is not necessary to test all lower numbers as possible factors, only lower primes up to the square root of $x. This is enabled by storing primes as they are found in an array (which I think is the strategy the OP was referring to).
从数学上讲，没有必要测试所有较小的数字作为可能的因子，只需测试直到 $x 平方根的较小素数。这是通过存储在数组中找到的素数来实现的（我认为这是 OP 所指的策略）。
As soon as the first prime factor is found, we know that $x is not prime, and so no further testing of that value of $x is needed and we can break out of the foreach loop.
一旦找到第一个素数因子，我们就知道 $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>";
}
