输入在一行中给出1个整数n(<= 10 000 000),对每一组输入，在一行中输出1~n的素数个数。用c++语言编程，要求运行时长最短的算法

以下是使用线性筛法（埃氏筛法）实现的C语言代码：

#include <stdio.h>
#include <stdbool.h>

#define MAXN 10000000

int prime[MAXN];    // 存放素数
bool is_prime[MAXN];    // 标记是否为素数

int main()
{
    int n;
    scanf("%d", &n);

    int cnt = 0;    // 记录素数个数
    for (int i = 2; i <= n; i++)
    {
        if (!is_prime[i])
        {
            prime[cnt++] = i;
        }
        for (int j = 0; j < cnt && i * prime[j] <= n; j++)
        {
            is_prime[i * prime[j]] = true;
            if (i % prime[j] == 0)    // 优化，避免重复标记
            {
                break;
            }
        }
    }

    printf("%d", cnt);

    return 0;
}

算法思想：从2开始遍历到n，若当前数未被标记为合数，则记录为素数并将其倍数标记为合数。具体实现中，使用一个数组存放素数，一个数组标记每个数是否为素数，初始都为false。遍历时，若当前数未被标记，则将其记录为素数，并将其倍数标记为合数。在标记倍数时，从已有素数中枚举，避免重复标记。最终素数个数即为数组中记录的素数个数。

算法时间复杂度：线性筛法的时间复杂度为O(n)。