0

我需要找到给定范围内的最高质数。
这是我的代码，适用于 0-100，但如果我给出 0-125，它将显示素数为 125。

<?php
    $flag=0;
    $b=125;
    for($i=$b;$i>=0;$i--)
    {
        if($i%2!=0)
        {
            for($b=3;$b<10;$b++)
            {
                if($flag==0)
                {
                    echo('<br>');
                    if($i%$b!=0)
                    {
                        echo('highest prime number is'.$i);
                        $flag=1;
                        break;
                    }
                    elseif ($i%$b==0)
                    {
                        break;
                    }
                }
            }
        }
    }
?>

在上面的代码中，我取的范围是 0-125

4

4 回答 4

5

gmp_nextprime()

<?php
$start = 125;
$stop = 0;
for($x=$start;$x>=$stop;$x--){
    if(($prime = gmp_intval(gmp_nextprime($x)))<$start){
        echo 'The highest prime is '.$prime;
        break;
    }
}?>
于 2012-12-26T08:06:16.593 回答
1

感谢您的回复 Samuel Cook ..但我需要不使用 'gmp_nextprime()' 函数.. iamgetting 消息 'Call to undefined function gmp_intval() in C:\wamp\www\highprime.php on line 5' – user1659450 16 mins前

由于您很难gmp functions上班，因此您可以使用

示例 1：无 GMP 功能

$range = range(125, 0); // create the range
foreach ( $range as $v ) {
    if (isPrime($v)) {
        printf('highest prime number is %d', $v);
        break;
    }
}

如果您能够使 gmp 正常工作，那么您可以使用gmp_prob_prime Function Used

示例 1：使用 gmp 函数

foreach ( $range as $v ) {
    if (gmp_prob_prime($v) == 2) {
        printf('highest prime number is %d', $v);
        break;
    }
}

输出 

highest prime number is 113

使用的功能 

function isPrime($num) {
    if ($num == 1)
        return false;

    if ($num == 2)
        return true;

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

    for($i = 3; $i <= ceil(sqrt($num)); $i = $i + 2) {
        if ($num % $i == 0)
            return false;
    }
    return true;
}
于 2012-12-26T08:37:53.290 回答
0

是的，问题是算法...

1）在这种情况下，您需要检查到sqrt($b)即 11

2）$flag逻辑有点混乱，没有用改变标志然后突然爆发......

<?php
        $flag=0;
        $b=125;
        $sq=sqrt($b); 

        for($i=$b;$i>=0;$i--)
        {

            if($i%2!=0)
            {
                    for($b=3;$b<=$sq;$b++)
                    {
                            if($i%$b!=0)
                            {
                                $flag=1;
                            }
                            elseif($i%$b==0)
                            {
                                $flag=0;
                                break;
                            }
                    }
            if($flag==1){ 
                echo('highest prime number is '.$i);  
                break;
            }
        }
    }
?>
于 2012-12-26T08:30:06.740 回答
0

您可以使用的最简单的方法是将一个从 3 开始的数字除以一个由 2 填充的数组，如果模数 (%) 给出的答案不是 0，则它是质数。然后在你得到一个工作代码之后，想想我能做什么更好？

  • 你可以说我想忽略偶数！那么为什么要迭代呢？只需使用 i = i + 2 （并从使用 3 作为种子素数开始）
  • 我除数太多了！你真的需要检查 21%11, 21%13, 21%17, 21%19 吗？它们总是小于 2，所以让我们忽略 > 一半的素数
  • 优化更多？在您的代码中限制使用根作为最大值会如何影响它？为什么？
  • 甚至更多？为什么我不能事先消除所有非素数并检查剩下的？

尝试将这些应用到您的代码上，或者只是谷歌一个工作版本。

于 2012-12-26T09:16:50.823 回答