C语言—打印100~200之间的素数的三种方法

摘要

素数是指只能被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之间的素数的三种方法