摘要
素数是指只能被1和自身整除的自然数。本篇博客将介绍三种方法在C语言中打印100~200之间的素数。
方法一:暴力穷举
暴力穷举是一种比较直观的方法,即从100开始遍历到200,对于每个数字判断是否为素数。
#include <stdio.h>
int isPrime(int num) {
if (num < 2) {
return 0;
}
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) {
return 0;
}
}
return 1;
}
int main() {
printf("100~200之间的素数有:\n");
for (int i = 100; i <= 200; i++) {
if (isPrime(i)) {
printf("%d ", i);
}
}
printf("\n");
return 0;
}
该方法中,使用isPrime
函数进行判断是否为素数。遍历范围内的每个数字,判断该数字是否能被其他数字整除,若能则不是素数,若不能则为素数。
方法二:埃氏筛法
埃氏筛法是一种更高效的算法,通过排除法筛选出素数。
#include <stdio.h>
#include <stdlib.h>
void printPrimes(int *numbers, int size) {
printf("100~200之间的素数有:\n");
for (int i = 0; i < size; i++) {
if (numbers[i]) {
printf("%d ", i + 100);
}
}
printf("\n");
}
void sieveOfEratosthenes(int *numbers, int size) {
numbers[0] = 0;
numbers[1] = 0;
for (int i = 2; i * i <= size; i++) {
if (numbers[i]) {
for (int j = i * i; j <= size; j += i) {
numbers[j] = 0;
}
}
}
}
int main() {
int size = 200 - 100 + 1;
int *numbers = (int *)malloc(size * sizeof(int));
for (int i = 0; i < size; i++) {
numbers[i] = 1;
}
sieveOfEratosthenes(numbers, size);
printPrimes(numbers, size);
free(numbers);
return 0;
}
该方法使用了埃氏筛法,首先初始化一个大小为101的数组numbers
,并将数组中所有元素初始化为1。然后从2开始遍历到根号200,将所有能被当前数字整除的数标记为0。最后遍历数组,输出所有值为1的索引值,即为素数。
方法三:优化的埃氏筛法
方法二中的埃氏筛法需要创建一个大小为101的数组来存储结果,可以进一步优化存储空间。
#include <stdio.h>
void printPrimes(int start, int end, int *primes) {
printf("100~200之间的素数有:\n");
for (int i = start; i <= end; i++) {
if (primes[i] == 1) {
printf("%d ", i);
}
}
printf("\n");
}
void sieveOfEratosthenes(int start, int end, int *primes) {
primes[0] = 0;
primes[1] = 0;
for (int i = 2; i * i <= end; i++) {
if (primes[i]) {
for (int j = i * i; j <= end; j += i) {
primes[j] = 0;
}
}
}
}
int main() {
int start = 100;
int end = 200;
int size = end - start + 1;
int *primes = (int *)calloc(size, sizeof(int));
sieveOfEratosthenes(start, end, primes);
printPrimes(start, end, primes);
free(primes);
return 0;
}
该方法和方法二类似,但不再使用动态分配内存,而是使用calloc
函数申请内存并将所有元素初始化为0。然后使用埃氏筛法,遍历过程中将素数对应的索引值设为1。最后输出值为1的索引值,即为素数。
结语
通过本篇博客,我们学习了三种方法在C语言中打印100~200之间的素数。这些方法分别是暴力穷举、埃氏筛法和优化的埃氏筛法。每种方法都有其优势和适用场景,可以根据实际情况选择适合的方法。希望本篇博客能对你理解C语言中素数的查找有所帮助。
本文来自极简博客,作者:星辰之海姬,转载请注明原文链接:C语言—打印100~200之间的素数的三种方法