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

题目：求100之内的素数。

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

方法1: 穷举法

解题思路:

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

实现代码:

#include <stdio.h>
#include <stdbool.h>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;
}

优缺点:

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

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

解题思路:

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

实现代码:

#include <stdio.h>
#include <stdbool.h>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;
}

优缺点:

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

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

解题思路:

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

实现代码:

#include <stdio.h>
#include <stdbool.h>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;
}