C语言练习百题之求100之内的素数

题目：求100之内的素数。

求解100以内的素数是一个常见的编程任务。素数是大于1且只能被1和自身整除的整数。我们将使用三种常见的方法来解决这个问题：穷举法、埃拉托斯特尼筛法和优化的埃拉托斯特尼筛法。

方法1: 穷举法

解题思路:

• 从2开始遍历每个数，对每个数判断是否为素数，判断方法是看是否能被比它小的数整除。
• 如果不能被任何比它小的数整除，则它是素数。

实现代码:

#include 
#include 

bool is_prime(int num) {
    if (num < 2)
        return false;

    for (int i = 2; i < num; i++) {
        if (num % i == 0)
            return false;
    }
    return true;
}

void print_primes(int limit) {
    for (int i = 2; i <= limit; i++) {
        if (is_prime(i))
            printf("%d ", i);
    }
}

int main() {
    int limit = 100;
    printf("Prime numbers up to %d:\n", limit);
    print_primes(limit);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

优缺点:

• 优点:
  • 算法简单，容易理解和实现。
• 缺点:
  • 效率较低，时间复杂度为O(n^2)。

方法2: 埃拉托斯特尼筛法

解题思路:

• 初始化一个布尔数组表示每个数是否为素数，初始所有数为素数。
• 从2开始，将所有的倍数标记为非素数。
• 最终剩下的未标记的数就是素数。

实现代码:

#include 
#include 

void sieve_of_eratosthenes(int limit) {
    bool is_prime[limit + 1];
    for (int i = 0; i <= limit; i++)
        is_prime[i] = true;

    for (int p = 2; p * p <= limit; p++) {
        if (is_prime[p]) {
            for (int i = p * p; i <= limit; i += p)
                is_prime[i] = false;
        }
    }

    printf("Prime numbers up to %d:\n", limit);
    for (int i = 2; i <= limit; i++) {
        if (is_prime[i])
            printf("%d ", i);
    }
}

int main() {
    int limit = 100;
    sieve_of_eratosthenes(limit);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

优缺点:

• 优点:
  • 算法效率较高，时间复杂度为O(n log log n)。
• 缺点:
  • 占用较多内存，空间复杂度为O(n)。

方法3: 优化的埃拉托斯特尼筛法

解题思路:

• 优化埃拉托斯特尼筛法，对每个素数的倍数进行标记时，从该素数的平方开始标记，而不是从素数的倍数开始。

实现代码:

#include 
#include 

void optimized_sieve_of_eratosthenes(int limit) {
    bool is_prime[limit + 1];
    for (int i = 0; i <= limit; i++)
        is_prime[i] = true;

    for (int p = 2; p * p <= limit; p++) {
        if (is_prime[p]) {
            for (int i = p * p; i <= limit; i += p)
                is_prime[i] = false;
        }
    }

    printf("Prime numbers up to %d:\n", limit);
    for (int i = 2; i <= limit; i++) {
        if (is_prime[i])
            printf("%d ", i);
    }
}

int main() {
    int limit = 100;
    optimized_sieve_of_eratosthenes(limit);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

优缺点:

• 优点:
  • 算法效率高，时间复杂度为O(n log log n)。
  • 占用较少内存，空间复杂度为O(n)。
• 缺点:
  • 需要理解和实现的优化较多，相对于简单埃拉托斯特尼筛法更复杂。

总结和推荐

• 推荐的方法: 优化的埃拉托斯特尼筛法
• 优化的埃拉托斯特尼筛法综合了效率和空间复杂度的优点，是求解素数的较好选择。
• 穷举法简单但效率低，不适用于大规模数据。
• 埃拉托斯特尼筛法是常用且高效的方法，占用较多内存。
• 优化的埃拉托斯特尼筛法在效率和内存占用上进行了平衡，是常用且推荐的方法。