c语言求质数因子

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的数，求质数的方法有很多，这里我们将介绍一种简单的方法，即埃拉托斯特尼筛法（Sieve of Eratosthenes）。

埃拉托斯特尼筛法是一种古老的筛选质数的方法，由古希腊数学家埃拉托斯特尼（Eratosthenes）于公元前3世纪提出，该方法的基本思想是：首先列出从2开始的所有自然数，然后从2开始，将2的倍数剔除，接着找到下一个未被剔除的数（即3），将3的倍数剔除，以此类推，直到所有小于等于给定上限的数都被剔除为止，最后剩下的数即为质数。

下面是一个使用C语言实现埃拉托斯特尼筛法的程序：

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#define MAX_NUM 1000000
bool is_prime[MAX_NUM + 1];
void sieve(int n) {
    memset(is_prime, true, sizeof(is_prime));
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }
}
int main() {
    int n = 1014; // 求1014以内的质数
    sieve(n);
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            printf("%d ", i);
        }
    }
    return 0;
}

程序首先定义了一个布尔数组is_prime，用于存储每个数是否为质数。sieve函数实现了埃拉托斯特尼筛法，将小于等于n的所有质数标记为true，非质数标记为false，在main函数中，我们调用sieve函数求出1014以内的质数，并将结果输出。

运行上述程序，我们可以得到1014以内的质数：2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113。