质数(素数)在线计算生成质数素数在线计算生成工具

使用步骤

1

输入范围

在下方输入框中输入要查找的最大数值（范围：2-100000）

2

点击计算

点击"生成质数"按钮，系统将自动筛选指定范围内的所有质数

3

查看结果

系统将显示所有找到的质数，并提供统计信息和导出功能

质数生成器

最大数值

提示：数值越大，计算时间越长，建议分批次生成

快捷选择

什么是质数？

质数（Prime number），又称素数，是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。换句话说，质数只有两个正因数：1和它本身。

质数的特征

最小的质数是 2
质数一定是奇数（除2以外）
任何大于1的非质数都可以分解为若干个质数的乘积（算数基本定理）
质数的个数是无限的（欧几里得证明）

100以内的质数

100以内的质数共有 25 个，分别是：

2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83、89、97

质数判定方法

1 试除法（最基础）

对于整数n，只需检查从2到√n的所有整数是否能整除n。如果都不能整除，则n是质数。

function isPrime($n) {
    if ($n < 2) return false;
    if ($n == 2) return true;
    if ($n % 2 == 0) return false;
    for ($i = 3; $i * $i <= $n; $i += 2) {
        if ($n % $i == 0) return false;
    }
    return true;
}

2 埃拉托斯特尼筛法（Sieve of Eratosthenes）

这是一种高效批量查找质数的方法。从2开始，将每个质数的倍数标记为非质数，直到√n为止。

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

3 6k±1 优化法

所有质数都可以表示为6k±1的形式（除2和3外）。因此在试除时只需检查形如6k±1的数。

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

质数的应用领域

密码学

RSA加密算法基于大数质数分解的困难性，是现代互联网安全的基础。所有HTTPS连接都依赖质数的数学特性。

哈希表

质数常用于哈希表的大小选择，可以减少哈希冲突，提高数据检索效率。

数论研究

质数分布规律的研究产生了黎曼猜想等世界级数学难题，推动了纯数学的发展。

伪随机数生成

线性同余生成器等伪随机数算法使用质数模数产生高质量的随机数序列。

质数(素数)在线计算生成