PHP에서 숫자가 소수인지 확인하는 세 가지 방법-PHP 튜토리얼-php.cn

PHP에서 숫자가 소수인지 확인하는 세 가지 방법

不言

풀어 주다： 2023-04-04 09:18:02

앞으로

5272명이 탐색했습니다.

이 기사는 PHP에서 숫자가 소수인지 확인하는 방법에 대한 세 가지 방법을 제공합니다. 이는 특정 참조 값을 가지고 있으므로 도움이 필요할 수 있습니다.

소수의 정의

소수는 소수라고도 합니다. 1과 자신 외에 다른 자연수를 나눌 수 없는 1보다 큰 자연수를 소수라고 하고, 그렇지 않으면 합성수라고 합니다.

구현 아이디어

가능한 모든 대체 숫자를 반복한 다음, 중간 숫자 이하이고 2보다 크거나 같은 정수로 정수 나누기 비교를 수행합니다. 정수로 나눌 수 있으면 확실히 소수가 아닙니다. 반대로 그것은 소수이다.

첫 번째 알고리즘

이것도 가장 먼저 떠오를 가능성이 높은데, 대안의 중간 숫자와 직접 비교해 보면 다음과 같습니다.

/**
 * 获取所有的质数
 * @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;
}

로그인 후 복사

### 두 번째 알고리즘

진심으로 말하면 이것은 또 다른 알고리즘이 아니며 첫 번째 알고리즘을 약간 최적화하고 비교 범위를 좁히기 위해 중간의 최대 수를 최적화한 것입니다. 알고리즘 소스 코드는 다음과 같습니다.

/**
 * 获取所有的质数
 * @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;
}

로그인 후 복사

세 번째 알고리즘

두 번째에도 해당됩니다. 이 최적화는 전체 배열에서 소수가 아닌 모든 숫자를 직접 삭제하는 것입니다. 알고리즘 소스 코드는 다음과 같습니다.

/**
 * 获取所有的质数
 * @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);
}

로그인 후 복사

사용 방법

예를 들어, 다음에서 모든 소수를 찾습니다. 1 ~ 100

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

로그인 후 복사

또 다른 예, 지정된 배열에서 숫자 찾기

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

로그인 후 복사

의 모든 소수

위 내용은 PHP에서 숫자가 소수인지 확인하는 세 가지 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!