编程求2~n(n为大于2的正整数,且小于等于50000)中有多少个素数用python怎么写
时间: 2024-05-09 16:17:40 浏览: 86
可以用以下代码实现:
```python
n = int(input("请输入一个大于2小于等于50000的正整数:"))
count = 0
for i in range(2, n+1):
if all(i % j != 0 for j in range(2, int(i**0.5)+1)):
count += 1
print("在2~{}中有{}个素数".format(n, count))
```
这段代码利用 for 循环从 2 至 n 遍历每个数字,然后用 all 函数判断该数字是否为素数,若为素数则计数器 count 加 1。最后输出结果。
相关问题
编程求2~n(n为大于2的正整数,且小于等于50000)中有多少个素数python。
以下是 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),因此该算法的效率非常高,可以在瞬间完成计算。
编程求2~n(n为大于2的正整数,且小于等于50000)中有多少个素数,输入格式输入,n(2≤n≤50000)。输出格式素数个数。用python怎么写
你好!关于你的问题,我可以直接回答,下面是Python代码:
```python
n = int(input())
is_prime = [True] * (n+1) # 标记每个数是否为素数
is_prime[0] = is_prime[1] = False # 0和1不是素数
# 从2开始,标记素数的倍数
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
# 统计素数个数
count = sum(1 for x in is_prime if x)
print(count)
```
这段代码使用了埃拉托色尼筛法来判断素数,并统计素数个数。如果有任何问题,欢迎继续咨询我。
阅读全文