用筛选法求100之内的素数,将结果存放在一个一维数组中
时间: 2024-12-20 21:23:53 浏览: 11
筛选法,也称为埃拉托斯特尼筛法,是一种用于寻找一定范围内所有质数的有效算法。它的基本思想是从2开始,将每个质数的倍数标记为合数,然后继续查找下一个未被标记的数,这个数就是下一个质数。以下是用Python实现的一个简单版本:
```python
def sieve_of_eratosthenes(n):
primes = [True] * (n + 1)
primes[0], primes[1] = False, False # 0和1不是质数
for i in range(2, int(n**0.5) + 1): # 只需检查到√n
if primes[i]: # 如果i是质数
for j in range(i*i, n+1, i): # 将i的倍数标记为合数
primes[j] = False
prime_array = [num for num, is_prime in enumerate(primes) if is_prime]
return prime_array[:100] # 返回前100个质数
# 使用筛选法获取100以内的素数并存储在一维数组
prime_numbers = sieve_of_eratosthenes(100)
```
相关问题
C语言:用筛选法求100之内的素数,将结果存放在一个一维数组中
在C语言中,我们可以使用筛法(如埃拉托斯特尼筛法)来找出100以内的所有素数,并将它们存储在一个一维数组中。这里是一个简单的示例:
```c
#include <stdio.h>
#define MAX_PRIME 100
// 判断是否为素数的函数
int is_prime(int n) {
if (n <= 1)
return 0;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0)
return 0;
}
return 1;
}
// 筛选出100以内素数并将结果存入数组
void sieve_of_eratosthenes(int primes[MAX_PRIME]) {
int count = 0;
bool is_marked[MAX_PRIME + 1] = {false}; // 初始化标记数组
for (int i = 2; i <= MAX_PRIME; i++) {
if (!is_marked[i]) { // 如果i未被标记为合数
primes[count++] = i; // 将其添加到素数数组
for (int j = i * i; j <= MAX_PRIME; j += i) {
is_marked[j] = true; // 标记j的倍数为合数
}
}
}
primes[count] = 0; // 填充数组直到适当长度
}
int main() {
int prime_array[MAX_PRIME];
sieve_of_eratosthenes(prime_array);
printf("100以内的素数有:\n");
for (int i = 0; prime_array[i]; i++) {
printf("%d ", prime_array[i]);
}
printf("\n");
//
用筛选法求100之内的素数。(用数组完成)
筛选法,也称为埃拉托斯特尼筛法(Sieve of Eratosthenes),是一种古老的算法,用于寻找一定范围内所有的质数。在这个例子中,我们可以创建一个布尔数组,初始所有元素都标记为`true`,表示它们可能是质数。然后从2开始,将每个素数的倍数标记为非素数。最后,数组中仍然为`true`的索引就是素数。
以下是用Python语言实现这个过程的一个简单示例:
```python
def sieve_of_eratosthenes(n):
primes = [True] * (n + 1) # 初始化所有数为质数
primes[0], primes[1] = False, False # 0和1不是质数
for i in range(2, int(n**0.5) + 1): # 只需检查到√n
if primes[i]: # 如果i是质数
for j in range(i*i, n+1, i): # 将i的倍数标记为非质数
primes[j] = False
prime_numbers = [i for i, is_prime in enumerate(primes) if is_prime]
return prime_numbers[:100] # 返回前100个素数
# 示例结果
sieve_primes = sieve_of_eratosthenes(100)
print(sieve_primes)
阅读全文