Three ways to determine whether a number is prime in PHP

This article brings you three methods on how to determine whether a number is a prime number in PHP. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you. .

Definition of prime numbers

Prime numbers are also called prime numbers. A natural number greater than 1 that cannot be divided into other natural numbers except 1 and itself is called a prime number; otherwise it is called a composite number.

Implementation Idea

Loop through all possible alternative numbers, and then perform integer division comparisons with integers below the middle number and greater than or equal to 2. If it can be an integer, it is definitely not a prime number. On the contrary, it is prime numbers.

The first algorithm

This is also the most likely to come to mind first, that is, directly compare with the middle number of the alternatives. The algorithm source code is as follows:

/**
 * 获取所有的质数
 * @param array $arr
 * @return array
 */
function get_prime_number($arr = []) {
    // 质数数组
    $primeArr = [];
    // 循环所有备选数
    foreach ($arr as $value) {
        // 备选数和备选数的中间数以下的数字整除比较
        for ($i = 2; $i <= floor($value / 2); $i++) {
            // 能够整除，则不是质数，退出循环
            if ($value % $i == 0) {
                break;
            }
        }
        // 被除数$j比备选数的中间数大的则为质数
        // 这样判断的依据：
        // 假如备选数为质数，则内层的for循环不会break退出，则执行完毕，$i会继续+1，即最后$i = floor($value / 2) + 1
        // 假如备选数不为质数，则内层的for循环遇到整除就会break退出，$i不会继续+1，即最后$i <= floor($value / 2)
        if ($value != 1 && $i > floor($value / 2)) {
            $primeArr[] = $value;
        }
    }
    return $primeArr;
}

The second algorithm

Seriously speaking, this is not another algorithm. It is just a slight optimization of the first one and the optimization of the maximum number in the middle to narrow the comparison range. The algorithm source code is as follows ：

/**
 * 获取所有的质数
 * @param array $arr
 * @return array
 */
function get_prime_number($arr = []) {
    // 质数数组
    $primeArr = [];
    // 循环所有备选数
    foreach ($arr as $value) {
        // 备选数和备选数的中间数以下的数字整除比较
        for ($i = 2; $i <= floor($value / $i); $i++) {
            // 能够整除，则不是质数，退出循环
            if ($value % $i == 0) {
                break;
            }
        }
        // 被除数$j比备选数的中间数大的则为质数
        // 这样判断的依据：
        // 假如备选数为质数，则内层的for循环不会break退出，则执行完毕，$i会继续+1，即最后$i = floor($value / $i) + 1
        // 假如备选数不为质数，则内层的for循环遇到整除就会break退出且$i不会继续+1，即最后$i <= floor($value / $i)
        if ($value != 1 && $i > floor($value / $i)) {
            $primeArr[] = $value;
        }
    }
    return $primeArr;
}

The third algorithm

This is also an optimization for the second type, that is, all numbers that are not prime numbers can be directly deleted from the complete array. The algorithm source code is as follows:

/**
 * 获取所有的质数
 * @param array $arr
 * @return array
 */
function get_prime_number_three($arr = []) {
    // 质数数组
    $primeArr = $arr;
    // 循环所有备选数
    foreach ($primeArr as $key => $value) {
        if ($value == 1) {
            unset($primeArr[$key]);
            continue;
        }
        // 备选数和备选数的中间数以下的数字整除比较
        for ($i = 2; $i <= floor($value / $i); $i++) {
            // 能够整除，则不是质数，从数组中删除且退出循环
            if ($value % $i == 0) {
                unset($primeArr[$key]);
                break;
            }
        }
    }
    // 重置数组索引返回
    return array_values($primeArr);
}

Usage method

For example, find all the prime numbers from 1 to 100

// 所有备选数数组
$numberArr = range(1, 100, 1);
// 获取备选数中的所有质数
$primeNumberArr = get_prime_number($numberArr);
// 输出打印
print_r($primeNumberArr);

Another example, find all the prime numbers in the specified array###

// 所有备选数数组
$numberArr = [11, 22, 33, 66, 77, 3, 8, 10, 99];
// 获取备选数中的所有质数
$primeNumberArr = get_prime_number($numberArr);
// 输出打印
print_r($primeNumberArr);

The above is the detailed content of Three ways to determine whether a number is prime in PHP. For more information, please follow other related articles on the PHP Chinese website!