编写程序,求一到一百范围内的所有素数
时间: 2023-10-07 12:07:05 浏览: 40
这里提供两种不同的方法来求解一到一百范围内的所有素数。
方法一:暴力枚举法
这种方法比较直接,就是从2到100枚举每个数,并判断它是否是素数。一个数n是否是素数,可以用从2到n-1的每个数去除它,如果都不能整除,那么n就是素数。
以下是Python代码实现:
```python
for i in range(2, 101):
is_prime = True
for j in range(2, i):
if i % j == 0:
is_prime = False
break
if is_prime:
print(i, end=' ')
```
输出结果:
```
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
```
方法二:筛法
筛法的思想是从小到大枚举每个数,如果这个数是素数,那么它的倍数一定不是素数。因此,我们可以用一个数组来记录每个数是否是素数,然后从2开始枚举,将它的所有倍数标记为非素数。最后,数组中标记为素数的数就是素数。
以下是Python代码实现:
```python
is_prime = [True] * 101
is_prime[0] = is_prime[1] = False
for i in range(2, 101):
if is_prime[i]:
for j in range(i * i, 101, i):
is_prime[j] = False
for i in range(2, 101):
if is_prime[i]:
print(i, end=' ')
```
输出结果:
```
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
```
这种方法的时间复杂度是O(nloglogn),比暴力枚举法要优秀得多。