Use script to find prime numbers in php

In computer science, a prime number refers to a positive integer that is only divisible by 1 and itself. Prime numbers can be used in fields such as encryption, mathematical derivation, and algorithm optimization. In practical applications, the algorithm for finding prime numbers is also one of the very important knowledge points. Today we will discuss how to use scripts in PHP to find prime numbers.

1. Screening method

The screening method is a classic algorithm for finding prime numbers. Its core idea is to continuously filter out numbers that are not prime numbers, and what is left in the end is a prime number. The specific steps are as follows:

1. Initialize a prime array $prime = array(), and put numbers from 2 to n (n is the required range) into it.
2. For the number 2~sqrt(n) (sqrt(n) represents the square root of n), determine whether it is a prime number in turn. If so, remove its multiples from the prime number array.
3. After the loop ends, the remaining numbers in the prime array are all the prime numbers.

The implementation code is as follows:

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 is an important number theory theorem that can be used Determine whether a number is prime. Fermat's Little Theorem is expressed as follows: If p is a prime number and a is any integer, then a^(p-1)≡1(mod p).

The specific steps are as follows:

1. Randomly select a number a and determine whether a and n are mutually prime. If they are not mutually prime, return false directly.
2. Calculate the value of a^(n-1) mod n. If it is not equal to 1, return false.
3. After many tests, if the above two conditions are met, then n is likely to be a prime number.

The implementation code is as follows:

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;
}

The above are two methods of finding prime numbers using scripts in PHP. It should be noted that the screening method is often more efficient than Fermat's Little Theorem when solving a large range of prime numbers.

The above is the detailed content of Use script to find prime numbers in php. For more information, please follow other related articles on the PHP Chinese website!