php如何实现质数

PHP 实现质数的方法

质数是指大于1的自然数，除了1和它本身外没有其他约数。以下是几种在PHP中实现质数判断和生成的方法：

判断一个数是否为质数

使用循环和条件判断来检查一个数是否为质数：

function isPrime($num) {
    if ($num <= 1) {
        return false;
    }
    for ($i = 2; $i <= sqrt($num); $i++) {
        if ($num % $i == 0) {
            return false;
        }
    }
    return true;
}

// 示例
$number = 17;
if (isPrime($number)) {
    echo "$number 是质数";
} else {
    echo "$number 不是质数";
}

生成指定范围内的质数

生成从2到某个上限之间的所有质数：

function generatePrimes($max) {
    $primes = [];
    for ($i = 2; $i <= $max; $i++) {
        if (isPrime($i)) {
            $primes[] = $i;
        }
    }
    return $primes;
}

// 示例
$maxNumber = 50;
$primeNumbers = generatePrimes($maxNumber);
print_r($primeNumbers);

使用埃拉托斯特尼筛法（高效生成质数）

埃拉托斯特尼筛法是一种更高效的生成质数的方法：

function sieveOfEratosthenes($n) {
    $prime = array_fill(0, $n + 1, true);
    $prime[0] = $prime[1] = false;
    for ($p = 2; $p * $p <= $n; $p++) {
        if ($prime[$p]) {
            for ($i = $p * $p; $i <= $n; $i += $p) {
                $prime[$i] = false;
            }
        }
    }
    $primes = [];
    for ($i = 2; $i <= $n; $i++) {
        if ($prime[$i]) {
            $primes[] = $i;
        }
    }
    return $primes;
}

// 示例
$limit = 100;
$primes = sieveOfEratosthenes($limit);
print_r($primes);

优化质数判断

对于较大的数，可以进一步优化质数判断：

function isPrimeOptimized($num) {
    if ($num <= 1) {
        return false;
    }
    if ($num <= 3) {
        return true;
    }
    if ($num % 2 == 0 || $num % 3 == 0) {
        return false;
    }
    $i = 5;
    while ($i * $i <= $num) {
        if ($num % $i == 0 || $num % ($i + 2) == 0) {
            return false;
        }
        $i += 6;
    }
    return true;
}

// 示例
$number = 7919;
if (isPrimeOptimized($number)) {
    echo "$number 是质数";
} else {
    echo "$number 不是质数";
}

实际应用示例

在项目中，可以将质数相关功能封装成类：

class PrimeNumber {
    public static function isPrime($num) {
        if ($num <= 1) {
            return false;
        }
        for ($i = 2; $i <= sqrt($num); $i++) {
            if ($num % $i == 0) {
                return false;
            }
        }
        return true;
    }

    public static function getPrimesUpTo($max) {
        $primes = [];
        for ($i = 2; $i <= $max; $i++) {
            if (self::isPrime($i)) {
                $primes[] = $i;
            }
        }
        return $primes;
    }
}

// 使用示例
$primes = PrimeNumber::getPrimesUpTo(50);
print_r($primes);

这些方法覆盖了质数判断和生成的基本需求，可以根据具体场景选择合适的方法。对于性能要求高的场景，推荐使用埃拉托斯特尼筛法或优化后的质数判断算法。