输入在一行中给出1个整数n(<= 10 000 000),对每一组输入，在一行中输出1~n的素数个数。

这道题可以使用埃氏筛法（Sieve of Eratosthenes）来求解。

埃氏筛法是一种简单的筛法，其基本思想是：从2开始，将每个素数的倍数都标记成合数，直到筛完所有小于等于n的数，剩下的未被标记的数均为素数。

具体实现时，可以使用一个布尔数组来标记每个数是否为素数，初始时所有数都为素数。从2开始，遍历到n/2，对于每个素数p，将p的倍数都标记成合数，这样筛完后未被标记的数即为素数。

以下是Python代码实现：

import math

def count_primes(n):
    """
    计算1~n的素数个数
    """
    is_prime = [True] * (n+1)  # 初始化所有数为素数
    count = 0  # 记录素数个数
    for i in range(2, n+1):
        if is_prime[i]:  # 如果i是素数
            count += 1
            j = i * 2  # 从2i开始筛掉i的倍数
            while j <= n:
                is_prime[j] = False
                j += i
    return count

n = int(input())
print(count_primes(n))

时间复杂度分析：对于每个素数p，需要筛掉n/p个数，因此时间复杂度为O(nloglogn)。