数据结构+求素数个数
时间: 2024-03-29 07:32:02 浏览: 28
数据结构是计算机中用来组织和存储数据方式。它可以帮助我们高效地操作和管理数据,提高程序的执行效率。常见的数据结构包括数组、链表、栈、队列、树、图等。
求素数个数是一个常见的数学问题,素数指的是只能被1和自身整除的正整数。求素数个数的方法有很多,其中一种常见的方法是使用筛选法(埃氏筛法)。具体步骤如下:
1. 创建一个长度为n+1的布尔数组isPrime,并将所有元素初始化为true。
2. 将isPrime和isPrime设置为false,因为0和1不是素数。
3. 从2开始遍历到n,如果isPrime[i]为true,则将i的所有倍数(除了i本身)设置为false。
4. 统计isPrime数组中值为true的个数,即为素数的个数。
下面是一个示例代码,用于求解小于等于n的素数个数:
```python
def countPrimes(n):
isPrime = [True] * (n + 1)
isPrime[0] = isPrime[1] = False
for i in range(2, int(n ** 0.5) + 1):
if isPrime[i]:
for j in range(i * i, n + 1, i):
isPrime[j] = False
count = sum(isPrime)
return count
n = 100
prime_count = countPrimes(n)
print("小于等于", n, "的素数个数为:", prime_count)
```