Найти наибольшее простое число в заданном диапазоне

Question

Мне нужно найти наибольшее простое число в данном диапазоне.
Вот мой код, который работает для 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

Answer 1

Да проблема в алгоритмическом...

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

Answer 2

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

Answer 3

спасибо за ваш ответ, Сэмюэль Кук.. но мне нужно без использования функции 'gmp_nextprime()'.. сообщение для слежения 'вызов неопределенной функции gmp_intval() в C:\wamp\www\highprime.php в строке 5' - user1659450 16 минут тому назад

Так как у вас трудно получить 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Используемая функция

Пример 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;
}

Answer 4

Самый простой метод, который вы можете использовать, это разделить число, начинающееся с 3, с массивом, заполненным 2, если модуль (%) дает ответ, отличный от 0, это простое число. Тогда после того, как вы получили рабочий код, подумайте, что я могу сделать лучше?

• Можно сказать, я хочу игнорировать четные числа! так зачем перебирать чем вообще? просто используйте i = i + 2 (и начните с использования 3 в качестве начального числа)
• Я делю слишком много чисел! вам действительно нужно проверить 21%11, 21%13, 21%17, 21%19? Они всегда меньше 2, поэтому давайте проигнорируем простые числа> половины
• Оптимизировать больше? Как бы ограничить использование рута, как максимум в вашем коде повлияет на это? и почему?
• Даже больше? почему я не могу заранее исключить все простые числа и проверить, что осталось?

Попробуйте применить их в своем коде или просто Google рабочую версию.