素数是指除了 1 和自身外，不能被其他整数整除的自然数。其特点包括：任何大于 1 的自然数可分解成素数乘积、每个素数仅有一个正因子 1、素数个数无穷多。寻找素数的方法有：埃拉托斯特尼筛选法、费马小定理、米勒-拉宾素性检测。判断素数的方法是：使用素数表查找或使用素性检测算法测试。素数在密码学、数据压缩、随机数生成和数学问题解决中有着广泛应用。

什么是素数

素数是指除了 1 和自身以外，不能被任何整数整除的自然数。

素数的特点

• 任何一个大于 1 的自然数都可以分解成素数的乘积（称为质因数分解）。
• 每个素数都有且仅有一个正因子，即 1。
• 素数个数无穷多。

寻找素数的方法

• 埃拉托斯特尼筛选法：从 2 开始，依次将所有偶数标记为非素数，然后从 3 开始每隔 2 个数标记为非素数，依次类推，直到标记完所有数。剩下的未标记的数即为素数。
• 费马小定理：如果 p 是素数，a 是任意整数，则 a^p ≡ a (mod p)。
• 米勒-拉宾素性检测：使用随机数进行高效的素性测试算法。

判断给定数字是否为素数

• 使用埃拉托斯特尼筛选法生成素数表，然后查找给定数字是否在表中。
• 使用费马小定理或米勒-拉宾素性检测进行测试。

素数的应用

• 密码学（加密和解密）
• 数据压缩
• 随机数生成
• 数学问题解决