100种算法【Python版】第13篇——埃拉托斯特尼素数筛法

本文目录

• 1 基本原理
• 2 算法步骤
• • 2.1 初始化：
  • 2.2 标记非素数：
  • 2.3 收集素数：
• 3 数学示例
• 4 python代码

1 基本原理

埃拉托斯特尼筛法（Sieve of Eratosthenes）是一种经典的算法，用于高效地寻找一定范围内的所有素数。该算法以古希腊数学家埃拉托斯特尼命名，具有简单易懂和高效的特点。

• 素数的定义
  素数是大于1的自然数，且仅有两个正因数：1和它本身。例如，2、3、5、7、11等都是素数。
• 数的倍数
  对于任何一个素数 p p p，其倍数