C语言算法练习之数组求素数

概述

本篇文章将介绍如何使用C语言实现数组求素数的算法。素数，又称质数，是指除了1和它本身以外，不能被其他自然数整除的正整数。本篇文章的算法流程如下：输入一个正整数n，计算出小于等于n的所有素数，将它们存储在一个数组中，并输出这些素数。该算法将使用C语言实现。

算法实现

1. 定义函数

首先，我们需要定义一个函数来计算小于等于n的所有素数，并将它们存储在一个数组中。函数的定义如下：

void getPrime(int n, int prime[]);

上述函数的参数包括一个整数n，表示要计算小于等于n的所有素数；一个整型数组prime[]，用于存储小于等于n的所有素数。

2. 编写函数体

接下来，我们需要在函数中编写算法实现的代码。算法的具体流程如下：

1. 初始化一个布尔类型的数组isPrime[]，其长度为n+1，用于标记每个数是否为素数。初始化时将isPrime[0]和isPrime[1]的值设置为false，其余的值设置为true。
2. 遍历数组isPrime[]，从2开始，将小于等于n的所有素数和它们的倍数标记为false，即将isPrime[i]的值设置为false。
3. 遍历数组isPrime[]，将值为true的元素添加到数组prime[]中，以得到所有小于等于n的素数。

以下是上述算法的代码实现：

void getPrime(int n, int prime[]) {
    bool isPrime[n+1];
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = false;
    isPrime[1] = false;
    for (int i=2; i*i<=n; i++) {
        if (isPrime[i]) {
            for (int j=i*i; j<=n; j+=i) {
                isPrime[j] = false;
            }
        }
    }
    int index = 0;
    for (int i=2; i<=n; i++) {
        if (isPrime[i]) {
            prime[index++] = i;
        }
    }
}

3. 测试函数

最后，我们可以在主函数中调用getPrime()函数进行测试。以下是一个测试示例：

#include <stdio.h>

void getPrime(int n, int prime[]);

int main() {
    int n = 100;
    int prime[n];
    getPrime(n, prime);
    for (int i=0; i<n; i++) {
        if (prime[i] != 0) {
            printf("%d ", prime[i]);
        }
    }
    return 0;
}

上述示例中，我们测试了小于等于100的所有素数，并将它们输出到控制台。

总结

通过本篇文章的讲解，我们了解了如何使用C语言实现数组求素数的算法。该算法可以列举出小于等于n的所有素数，并存储在一个数组中。通过实例说明，我们学习了如何定义函数、编写函数体以及测试函数的方法。在实际应用中，我们可以使用该算法来解决涉及大量质数计算的问题。