求素数的个数。本题要求编写一个程序，求1~n的素数个数。 要求至少给出两种解法，对于相同的n，给出这两种解法的结果，通过相关数据进行测试，目的是通过对比同一问题不同解法的绝对执行时间体会如何设计“好”的算法。 输入格式: 输入在一行中给出1个整数n(<= 10 000 000)。 输出格式: 对每一组输入，在一行中输出1~n的素数个数。

以下是两种解法：

解法一：暴力枚举法

时间复杂度：O(n^2)

代码如下：

n = int(input())
count = 0
for i in range(2, n+1):
    flag = True
    for j in range(2, i):
        if i % j == 0:
            flag = False
            break
    if flag:
        count += 1
print(count)

解法二：埃氏筛法

时间复杂度：O(nloglogn)

代码如下：

n = int(input())
is_prime = [True] * (n+1)
count = 0
for i in range(2, n+1):
    if is_prime[i]:
        count += 1
        for j in range(i*i, n+1, i):
            is_prime[j] = False
print(count)

对于n=10000000，两种解法的执行时间分别为：

- 解法一：约为10秒
- 解法二：约为1秒

可以看出，解法二的执行时间远远优于解法一，这是因为解法二利用了埃氏筛法的思想，避免了重复计算，从而提高了效率。