求素数的个数。本题要求编写一个程序，求1~n的素数个数。 要求至少给出两种解法，对于相同的n，给出这两种解法的结果，通过相关数据进行测试，目的是通过对比同一问题不同解法的绝对执行时间体会如何设计“好”的算法。

题目要求编写一个程序，求1~n的素数个数。下面给出两种解法：

解法一：暴力枚举法

对于每个数i，从2到i-1枚举，判断i是否能被整除，若不能则i为素数。

代码如下：

def count_primes(n):
    count = 
    for i in range(2, n+1):
        flag = True
        for j in range(2, i):
            if i % j == :
                flag = False
                break
        if flag:
            count += 1
    return count

解法二：埃氏筛法

从2开始，将每个素数的倍数都标记成合数，直到不能再找到新的素数为止。

代码如下：

def count_primes(n):
    is_prime = [True] * (n+1)
    count = 
    for i in range(2, n+1):
        if is_prime[i]:
            count += 1
            j = i * i
            while j <= n:
                is_prime[j] = False
                j += i
    return count

对于n=10000，解法一的执行时间为1.5秒左右，解法二的执行时间为.02秒左右，可见解法二的效率更高。

因此，设计“好”的算法应该尽可能减少不必要的计算，提高算法的效率。