统计1~2^n 即[1, 2^n]之间素数的个数,n从键盘输入,及素数在全部数中的占比,以单进程方式编写,并输出程序运行的耗时
时间: 2024-12-18 16:38:03 浏览: 2
统计1到2^n范围内的素数个数以及素数在整个区间中的占比,可以通过著名的埃拉托斯特尼筛法(Sieve of Eratosthenes)实现。这是一种单进程的方法,通过创建一个布尔数组标记每个数字是否为素数,然后逐个筛选出所有素数。
以下是Python的示例代码:
```python
import time
def is_prime(n):
if n <= 1:
return False
elif n == 2 or n == 3:
return True
elif n % 2 == 0 or n % 3 == 0:
return False
i = 5
w = 2
while i * i <= n:
if n % i == 0:
return False
i += w
w = 6 - w
return True
def count_primes(n):
limit = 2**n
primes = [True] * (limit + 1)
primes[0] = primes[1] = False
for i in range(2, int(limit ** 0.5) + 1):
if primes[i]:
for j in range(i * i, limit + 1, i):
primes[j] = False
count = sum(primes)
prime_ratio = count / limit
return count, prime_ratio
# 获取用户输入
n = int(input("请输入n的值: "))
start_time = time.time()
count, ratio = count_primes(n)
end_time = time.time()
print(f"1到2^{n}之间的素数个数是: {count}")
print(f"素数在全部数中的占比是: {ratio*100:.2f}%")
print(f"程序运行耗时: {end_time - start_time:.4f}秒")
阅读全文