php怎么判断数据是质数 php怎么判断数据是质数的

判断一个数是否是质数

判断一个数是否是质数

创新互联公司专注为客户提供全方位的互联网综合服务，包含不限于网站设计、成都网站设计、鹤岗网络推广、微信平台小程序开发、鹤岗网络营销、鹤岗企业策划、鹤岗品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等，从售前售中售后，我们都将竭诚为您服务，您的肯定，是我们最大的嘉奖；创新互联公司为所有大学生创业者提供鹤岗建站搭建服务，24小时服务热线：18982081108，官方网址：www.cdcxhl.com

最暴力的解法

利用质数的性质：设i为质数，则i只能被 1 和 i整除。

因此对于i，我们可以令 2..i-1 依次除以i，如果均不能被整除，则说明是质数。

代码如下

private static boolean isPrime1(int nr) {

for (int i = 2; i nr; i++) {

if (nr % i == 0) return false;

}

return true;

}123456123456

稍微暴力的方法

同样利用其性质，但我们可以注意到，当 x i / 2 时，则 x 肯定不能被 i 整除。

对于i，我们可以令 2..x 依次除以i，其中x为sqrt(i)

代码如下

private static boolean isPrime2(int nr) {

for (int i = 2; i*i = nr; i++) {

if (nr % i == 0) return false;

}

return true;

}123456123456

效率更高的算法

提供一个数组 nums = {2, 3, 4, 5,... 17}

我们知道 nums[0] 为质数，将nums中所有能被nums[0]整除的数移除，此时数组为 nus = {2, 3, 5, 7, 9, 11, 13, 15, 17}

接着将所有能被 3 整除的数移除。此时为 nums = {2, 3, 5, 7, 11, 13, 17}

接下来的数是 5，因为 5*5 17，所以移除过程结束。此时的nums值为输入nums中的所有素数。

上面的步骤之所以正确是因为：合数必定可以由质数相乘得到，则对任意质数i，如迹谨运果其不能被sqrt(i)前的所有质数整除，则其必定为质数晌旦（小于 sqrt(i) 的合数必定可以被小于 sqrt(i) 的质数合成）。

代码如下

private static void primeList(ListInteger nums) {

for (int i = 0; i nums.size(); i++) {

if (nums.get(i)*nums.get(i) = nums.get(nums.size()-1)) {

for (int j = i+1; j nums.size(); j++) {

if (nums.get(j) % nums.get(i) == 0) nums.remove(j);

}

} else {

return ;

}

}

}12345678910111234567891011

此算法存在的问题也很明显，说它是判断一个数是否是质数获取不太准确，其作用应该是 “打印出小于等于某值的所有质数”

使用素数表

上面的算法有一个缺陷，它对输入数组要求较高，要求包含了数组最大值之前的所有素数，且是已排序的。也就是说它不能用来直接判断一个数是否是素数。

通常情况下，我们会使用一个姿梁素数表。接着用来整除的元素便可以从这个素数表中获取

这种算法的局限在于素数表是有限的，对于超出素数表最大值平方的数则需要加上上述方法二的步骤才能判断（尽管这种情况不多）。

算法实现同上，只是此时直接从素数表获取素数即可

;fps=1

php判断一个数是否为素数

function selectnum($num){

for ($j = 2; $j  sqrt($num); $j++) {

仿陆     if ($num % $j == 0) {

return false;

}

}

return true;

}

判断是不是 素数 ，若 返回true 就是 素数，因为 若一个数能被整除，那肯定就不是素数！！！

加平方根验证（sqrt）的目的，是为了优化性能，因为：

如果它不是质数，那么它应该可以表示成两个非1非自身的数相乘。

而这两个数，必然有一个大于平方根一个小于平方根，或者两个都等于平方根。

下面是 获取 1000000 内 所有的 素数 ，在PHP7下 能做到2.3秒，  在5下 不到4秒！

public function test()

{

$start_time = microtime(true);

set_time_limit(0);

$num_max = 1000000;

$arr = [] ;

裂桥for ($i = 1;($i*6) = $num_max; $i++) {

$base=$i*6;

$num=$base-1;

$sta=$this-testnum($num);

if ($sta) {

$arr[$num]=1;

}

$num=$base+1;

$sta=$this-testnum($num);

if ($sta) {

$arr[$num]=1;

}

}

$end = microtime(true);

$zong = $end -$start_time;

echo '开始' . $start_time . 'br/' ;

echo '结束' . $end . 'br/' ;

echo '用时' . $zong  . 'br/';

echo '共' . count($arr) . '个素数';

}

function testnum($num){

for ($j = 2; $j  sqrt($num); $j++) {

if ($num % $j == 0) {

return 肆大猛false;

}

}

return true;

}