c语言如何利用线性塞求1到一亿的每个数的约数个数

在C语言中，计算从1到一亿每个整数的约数个数通常需要一些高效的算法，比如埃拉托斯特尼筛法（Sieve of Eratosthenes）。这种方法可以用于找出所有小于或等于给定范围内的素数，进而统计非素数的因数个数。以下是基本步骤：

1. 首先，创建一个足够大的布尔数组`isPrime[100000001]`，初始化所有的值为`true`。这将标记哪些数字是素数。

2. 使用埃拉托斯特尼筛法遍历数组：
- 从第一个素数2开始，将所有2的倍数标记为非素数（即`isPrime[i] = false`，i从4开始每次加2）。
- 然后找到下一个未被标记为非素数的数（即下一个素数），继续这个过程直到`sqrt(100000001)`（因为大于此范围的因子必然有一个小于或等于它的平方根）。
- 对于每个素数，只需更新它之后的所有偶数的计数即可。

3. 当筛法完成时，对剩余的非素数（即其索引`i`对应的值`isPrime[i] == false`），它们的因数个数就是它们本身减去1（因为每个非素数都有1作为因数）。

4. 最后，你需要记录并返回每个非素数的因数个数。你可以创建另一个数组`count`，并将结果存储在对应位置。

以下是简单的伪代码形式：

#include <stdio.h>
#include <math.h>

int main() {
    int n = 100000001;
    bool isPrime[n];
    for (int i = 0; i <= n; i++) {
        isPrime[i] = true;
    }

    // 埃拉托斯特尼筛法
    for (int p = 2; p * p <= n; p++) {
        if (isPrime[p]) {
            for (int i = p * p; i <= n; i += p) {
                isPrime[i] = false;
            }
        }
    }

    // 计算并记录因数个数
    int count[n];
    for (int i = 1; i < n; i++) {
        if (!isPrime[i]) {
            count[i] = i / 2 - 1; // 因数包括1和自身，所以总数减1
        } else {
            count[i] = 0; // 素数没有除了1以外的因数
        }
    }

    // 输出每个数的因数个数
    for (int i = 1; i < n; i++) {
        printf("Number %d has %d factors.\n", i, count[i]);
    }

    return 0;
}