스크립트를 사용하여 PHP에서 소수 찾기

컴퓨터 과학에서 소수는 1과 자기 자신으로만 나누어지는 양의 정수를 의미합니다. 소수는 암호화, 수학적 파생, 알고리즘 최적화 등의 분야에서 사용될 수 있습니다. 실제 응용 프로그램에서 소수를 찾는 알고리즘은 매우 중요한 지식 포인트 중 하나입니다. 오늘 우리는 소수를 찾기 위해 PHP에서 스크립트를 사용하는 방법에 대해 논의하겠습니다.

1. 스크리닝 방법

스크리닝 방법은 소수를 찾는 고전적인 알고리즘으로 소수가 아닌 숫자를 계속해서 걸러내고 결국 남는 것은 소수입니다. 구체적인 단계는 다음과 같습니다.

1. 소수 배열 $prime = array()를 초기화하고 2부터 n까지의 숫자(n은 필수 범위)를 입력합니다.
2. 숫자 2~sqrt(n)(sqrt(n)은 n의 제곱근을 나타냄)에 대해 차례로 소수인지 확인합니다. 그렇다면 소수 배열에서 배수를 제거합니다.
3. 루프가 끝난 후 소수 배열에 남아 있는 숫자는 모두 소수입니다.

구현 코드는 다음과 같습니다.

function sieve($n) {
    $prime = array();
    for($i = 2; $i <= $n; ++$i) {
        $prime[$i] = true;
    }
    for($i = 2; $i <= sqrt($n); ++$i) {
        if($prime[$i]) {
            for($j = $i*$i; $j <= $n; $j += $i) {
                $prime[$j] = false;
            }
        }
    }
    return array_keys(array_filter($prime));
}

2. Fermat's Little Theorem

Fermat's Little Theorem은 숫자가 소수인지 여부를 결정하는 데 사용할 수 있는 중요한 정수론 정리입니다. 페르마의 작은 정리(Fermat's Little Theorem)는 다음과 같이 표현됩니다: p가 소수이고 a가 임의의 정수이면 a^(p-1)=1(mod p)입니다.

구체적인 단계는 다음과 같습니다.

1. 숫자 a를 무작위로 선택하고 a와 n이 서로 소수인지 확인합니다. 서로 소수가 아닌 경우 false를 직접 반환합니다.
2. a^(n-1) mod n의 값을 계산하고, 1이 아니면 false를 반환합니다.
3. 많은 테스트를 거쳐 위의 두 조건이 충족되면 n이 소수일 가능성이 높습니다.

구현 코드는 다음과 같습니다.

function is_prime($n) {
    if($n <= 1) {
        return false;
    }
    for($i = 0; $i < 10; ++$i) {
        $a = rand(1, $n-1);
        if(gcd($a, $n) != 1) {
            return false;
        }
        if(mod_pow($a, $n-1, $n) != 1) {
            return false;
        }
    }
    return true;
}

function gcd($a, $b) {
    return ($b == 0) ? $a : gcd($b, $a%$b);
}

function mod_pow($base, $exp, $modulus) {
    $result = 1;
    while($exp > 0) {
        if($exp % 2 == 1) {
            $result = ($result * $base) % $modulus;
        }
        $exp = $exp >> 1;
        $base = ($base * $base) % $modulus;
    }
    return $result;
}

위는 PHP에서 스크립트를 사용하여 소수를 찾는 두 가지 방법입니다. 넓은 범위의 소수를 풀 때 스크리닝 방법이 페르마의 작은 정리보다 더 효율적인 경우가 많다는 점에 유의해야 합니다.

위 내용은 스크립트를 사용하여 PHP에서 소수 찾기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!