时间戳

首页 > 解决方案 > 什么是 gmp_nextprime 算法？

php - 什么是 gmp_nextprime 算法？

问题描述

我目前正在重新学习很多 PHP，并且遇到了 gmp。

我知道gmp可以添加到PHP中，但是如果不能呢？

通常的主要上市方法包括：

$max = 10;
for( $prime = 2; $prime <= $max; $prime++ ) {
    for( $count = 2; $count < $prime; $count++ ) {
        if( $prime % $count == 0 ) {
            break;
        }
    }
    if( $count == $prime )
        echo "Prime: ", $prime, "<br>";
    }
}

达到数千时非常慢。

对于 gmp，它只需要几毫秒。

它的算法是什么？

它如何找到下一个素数？

标签： phpgmp

解决方案

链接在这里。http://php.net/manual/en/function.gmp-nextprime.php

此函数使用概率算法来识别素数，获得合数的机会非常小。

此报价来自链接。该链接指定该函数使用概率算法。该算法最终可能会得到合数。但是，机会极小。

还有一篇关于概率算法的好文章。

https://www.sciencedirect.com/science/article/pii/0022314X80900840

推荐阅读