编程求2～n（n为大于2的正整数，且小于等于50000）中有多少素数）

可以使用筛法求解，具体实现可以参考以下代码：

int countPrimes(int n) {
if (n <= 2) return 0;
vector<bool> isPrime(n, true);
int count = n - 2;
for (int i = 2; i * i < n; ++i) {
if (!isPrime[i]) continue;
for (int j = i * i; j < n; j += i) {
if (isPrime[j]) {
isPrime[j] = false;
--count;
}
}
}
return count;
}

该算法的时间复杂度为 O(nloglogn)，可以在较短时间内求解较大的 n。

相关问题

编程求2～n（n为大于2的正整数，且小于等于50000）中有多少个素数。

这道题可以使用埃氏筛法（Sieve of Eratosthenes）来解决，时间复杂度为O(nloglogn)。

具体思路是：首先初始化一个长度为n+1的布尔类型数组is_prime，用于标记每个数是否为素数，并把每个数字的初始状态都设置为True。然后，我们从2开始遍历到n的平方根，如果当前数字i为素数，则将i的倍数（除了i本身）标记为非素数。最后遍历is_prime数组，统计标记为True的数字的个数即可。

以下是Python代码实现：

def count_primes(n):
    # 初始化一个长度为n+1的布尔类型数组，用于标记每个数是否为素数，初始值都为True
    is_prime = [True] * (n + 1)

    # 从2开始遍历到n的平方根，如果当前数字i为素数，则将i的倍数（除了i本身）标记为非素数
    for i in range(2, int(n ** 0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False

    # 统计标记为True的数字的个数
    count = 0
    for i in range(2, n + 1):
        if is_prime[i]:
            count += 1

    return count

在这个方法中，我们首先初始化一个长度为n+1的布尔类型数组is_prime，用于标记每个数是否为素数，并把每个数字的初始状态都设置为True。然后，我们从2开始遍历到n的平方根，如果当前数字i为素数，则将i的倍数（除了i本身）标记为非素数，这个过程中只需遍历到n的平方根的原因是，如果n不是素数，那么n一定可以分解为两个因子a和b，其中a和b至少有一个小于等于n的平方根，否则它们的乘积将大于n，与n是a和b的乘积矛盾。因此，我们只需要遍历到n的平方根，就可以判断出n是否为素数。

最后，我们遍历is_prime数组，统计标记为True的数字的个数即可。

编程求2～n（n为大于2的正整数，且小于等于50000）中有多少个素数python。

以下是 Python 代码实现：

def count_primes(n):
    if n < 3:
        return 0
    primes = [True] * n
    primes[0] = primes[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if primes[i]:
            primes[i*i:n:i] = [False] * len(primes[i*i:n:i])
    return sum(primes)

n = 50000
count = count_primes(n+1) - count_primes(2)
print(count)

解释：

首先定义一个 `count_primes` 函数，该函数使用埃拉托色尼筛法（Sieve of Eratosthenes）来计算小于等于 n 的所有素数的个数。然后计算 2～n（包含 n）中的素数个数，即 `count_primes(n+1) - count_primes(2)`。注意，这里需要加 1 是因为 `count_primes` 函数计算的是小于等于 n 的素数个数。

该算法的时间复杂度为 O(n log(log n))，空间复杂度为 O(n)。在本问题中，由于 n 取值较小（小于等于 50000），因此该算法的效率非常高，可以在瞬间完成计算。