10

我需要用 for 循环或 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;
}
?>

有没有办法将一个数字与一个数组相除以找到剩余的数字？

4

22 回答 22

39

这是我发现的一个小功能：（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;
}
于 2013-05-26T20:21:47.047 回答
13

你可以使用这个 PHP 函数gmp_nextprime()

于 2013-05-26T20:20:10.080 回答
8

这是我不久前发现的用于检查素数的单线。它使用计数标记（一元数学）来确定：

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++;
}
于 2014-07-15T22:53:07.230 回答
7

这是一个基本的实现：

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

完整的逻辑一步一步和视觉类比在这里： 这里

于 2014-04-07T16:56:00.740 回答
3

没有数学函数：

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

        return false;
    }

    return true;
}
于 2015-01-30T21:30:08.337 回答
3

我知道为时已晚，但我发现这个解决方案更优雅。

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

    return true;
}
于 2016-10-17T21:03:06.053 回答
2

任何 sqrt() 为假或任何浮点值都是素数

于 2014-05-14T14:57:55.490 回答
1

我相信这是一个非常有效的例程，它列出了 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>";
}
于 2013-10-26T16:25:36.117 回答
1

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;
    }
于 2014-07-25T11:28:58.513 回答
1 
<?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/

于 2016-11-30T16:41:49.620 回答
1

下面的程序很简单，有两个 for 循环，在迭代中忽略 1 和 self 值。它将打印素数，

function get_primenumbers($length) {
    //Ignore 1
    for($i = 2; $i <= $length; $i++){
        $prime = true;
        for($j = 2; $j <= $i; $j++){
            //Ignore same number
            if(($i != $j) && ($i % $j == 0)){
                $prime = false;
                break;
            }
        }

        if(!$prime){
            echo "$i is not prime <br />";
        }else{
            echo "$i is prime <br />";
        }
    }
}
于 2019-06-05T06:46:07.990 回答
1 
$num = 25;
echo "Value Hardcored ".$num."<br>";

for($i=2; $i<$num; $i++)
 {
  if($num%$i==0)
  {
   $Loop = true;
   echo "This is Composite Number";
   break; 
  }
  $Loop = false; 
 }

 if($Loop == false)
 {
  echo "Prime Number";
 }
于 2020-09-02T01:34:47.977 回答
0

我知道这有点晚了，但希望它对某人有所帮助。

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

于 2014-04-09T13:57:28.097 回答
0 
$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';
}
于 2014-07-20T08:24:50.257 回答
0

使用 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不是质数

于 2015-11-02T11:06:02.680 回答
0

检查一个数是否为素数的最好方法是看它是否能被它之前的任何素数整除。Pi(x) 是我在任何地方都能看到的……你可以在wikipedia上看到更多关于 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 ) );
    }
}

这实际上不是很有效，嗯，不是在构建素数列表时...在线查找列表并使用它。

以上内容的使用将遵循以下原则：

$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";
}
于 2016-10-12T14:43:13.167 回答
0

我知道这有点晚了，但这里有一个简单的程序可以帮助你做你所要求的......

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

?>
于 2017-07-28T12:02:40.693 回答
0 
<?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);
?>
于 2017-08-11T12:47:22.853 回答
0

@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 数组将没有足够的历史记录。

于 2017-08-11T22:39:04.243 回答
0

这是另一种非常简单但安静有效的方法：

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);
于 2017-09-14T21:08:31.487 回答
0 
<?php 
$limit=100;

$i=1;


outer:while($i<=$limit){
    $j=2;
    while($j<$i){
        if($i%$j==0){
            $i++;
            goto outer;
        }
        $j++;
    }
    echo $i;
    echo "<br/>";
    $i++;
}


?>
于 2018-04-10T07:22:33.727 回答
0 
    <form method="post" action="">
    <input type="number" name="demo" placeholder="Enter Any Number">
    <button type="submit" name="aqeela" > Prime or composite </button>
    </form>
    <br>
    <?php
      if(isset($_POST['aqeela']))
       {
         $nu=$_POST['demo'];
         if($nu==2)
       {
          echo "The Only Even Prime Number";
       }
       else
       {
         for($i=2; $i<$nu; $i++)
       {
         if($nu%$i==0)
       {    
         echo "This is Composite Number";
         break;  
       }
       else
       {    
         if($i==($nu-1))
       { 
         echo "Prime number";
       }    
      }  
     }
    }
   }
于 2020-09-02T01:38:25.490 回答