求N以内(包括N)的素数。(N<= 100000)

可以使用筛法求解，时间复杂度为O(NloglogN)。

以下是代码：

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 1e5 + 5;
bool isPrime[MAXN];

int main() {
    int n;
    cin >> n;
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * 2; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            cout << i << " ";
        }
    }
    cout << endl;
    return 0;
}

相关问题

求n以内（包括n）的素数。(n<=100000)

这是一个求解质数的问题，可以使用筛法求解。具体步骤如下：

1. 创建一个长度为n+1的布尔数组，用来标记每个数是否为质数，初始值都为true。

2. 从2开始，将2的倍数（除2以外）标记为false，因为它们不是质数。

3. 从3开始，将3的倍数（除3以外）标记为false，因为它们不是质数。

4. 依次类推，对于每个未被标记为false的数i，将i的倍数（除i以外）标记为false。

5. 最后，所有未被标记为false的数就是小于等于n的质数。

代码实现如下：

def find_primes(n):
    is_prime = [True] * (n+1)
    is_prime[] = is_prime[1] = False
    for i in range(2, int(n**.5)+1):
        if is_prime[i]:
            for j in range(i*i, n+1, i):
                is_prime[j] = False
    primes = [i for i in range(n+1) if is_prime[i]]
    return primes

调用该函数即可得到小于等于n的所有质数。

用筛法求N之内的素数。(1<=N<=10000000)

好的，这是一个经典的算法问题。我们可以使用埃拉托色尼筛法（Sieve of Eratosthenes）来解决这个问题。

具体步骤如下：

1. 先创建一个长度为N+1的数组，用来记录每个数字是否是素数，初始值都为true。

2. 从2开始，将2的倍数（除2以外）都标记为false，因为它们不是素数。

3. 找到下一个未标记为false的数字p，将p的倍数（除p以外）都标记为false。

4. 重复步骤3，直到p²>N。

5. 遍历数组，输出所有标记为true的数字，即为N以内的素数。

以下是Python代码实现：

def sieve_of_eratosthenes(n):
    is_prime = [True] * (n+1)
    is_prime[0], is_prime[1] = False, False
    p = 2
    while p**2 <= n:
        if is_prime[p]:
            for i in range(p**2, n+1, p):
                is_prime[i] = False
        p += 1
    primes = [i for i in range(n+1) if is_prime[i]]
    return primes

调用`sieve_of_eratosthenes(N)`即可得到N以内的素数列表。