给定一个整数 n，让我们找出所有小于或等于 n 的质数。
示例：
> 输入： n = 10
> 输出： [2, 3, 5, 7]
> 解释： 通过埃拉托斯特尼筛法得到的 10 以内的质数为 [2, 3, 5, 7]。
>
> 输入： n = 35
> 输出： [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
> 解释： 通过埃拉托斯特尼筛法得到的 35 以内的质数为 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]。
目录
- [朴素方法] – 使用循环 O(n*sqrt(n)) 时间和 O(1) 空间
- [高效方法] – 埃拉托斯特尼筛法
[朴素方法] – 使用循环 O(n*sqrt(n)) 时间和 O(1) 空间
> 查找从 INLINECODE212a3787 到 INLINECODEb1cc724f 的所有质数的朴素方法，包括单独检查每个数字以确定它是否为质数。
逐步实现：
- 遍历从 INLINECODEfe8f54b3 到 INLINECODE67288fab 的所有数字
i。 - 对于每个 INLINECODEd26951b5，检查它是否可以被 INLINECODEe2d39f1d 到
i - 1之间的任何数字整除。 - 如果它可以被整除，则
i不是质数。 - 如果它不能被该范围内的任何数字整除，则
i是质数。
> 埃拉托斯特尼筛法通过从 2 开始，反复将每个质数的倍数标记为非质数，从而高效地找到所有直到 n 的质数。这避免了冗余检查，并快速过滤掉所有合数。
逐步实现：
- 初始化一个布尔数组 pINLINECODE27b4f81a，并将所有条目设置为 INLINECODE8eaf846e，但 INLINECODEd5f00f2c 和 INLINECODE711817e5 除外（它们不是质数）。
- 从 2 开始，这是最小的质数。
- 对于从 INLINECODE03e97baf 到 INLINECODE75ba0df7 的每个数字
p： - 如果
p被标记为质数： - 将 INLINECODE2ed5b41a 的所有倍数标记为非质数，从 INLINECODEe7e6e86b 开始（因为更小的倍数已经被更小的质数标记过了）。
- 循环结束后，pINLINECODE5aaee81d 数组中所有剩余为 INLINECODE53c87c52 的条目即代表质数。
C++
CODEBLOCK_0a890fbc
Java
CODEBLOCK_63db0e33
Python
CODEBLOCK_83b4ac41
C#
using System;
using System.Collections.Generic;
class GfG {
// Function to return all prime numbers up to n
static List sieve(int n) {
// Boolean array to mark primes
bool[] prime = new bool[n + 1];
for (int i = 0; i <= n; i++) {
prime[i] = true;
}
// Sieve of Eratosthenes
for (int p = 2; p * p <= n; p++)
{
if (prime[p])
{
f