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

以下是两种解法：

解法一：暴力枚举法

思路：对于每个数i，从2到i-1枚举，判断i是否能被整除，如果不能则i是素数。

代码如下：

#include <stdio.h>

int main()
{
int n, cnt = 0;
scanf("%d", &n);
for (int i = 2; i <= n; i++)
{
int flag = 1;
for (int j = 2; j < i; j++)
{
if (i % j == 0)
{
flag = 0;
break;
}
}
if (flag) cnt++;
}
printf("%d\n", cnt);
return 0;
}

解法二：埃氏筛法

思路：从2开始，将每个素数的倍数都标记成合数，直到筛完所有小于等于n的数。

代码如下：

#include <stdio.h>
#include <string.h>

int main()
{
int n, cnt = 0;
scanf("%d", &n);
int prime[n+1];
memset(prime, 1, sizeof(prime));
for (int i = 2; i <= n; i++)
{
if (prime[i])
{
cnt++;
for (int j = i*2; j <= n; j += i)
{
prime[j] = 0;
}
}
}
printf("%d\n", cnt);
return 0;
}

测试数据：

输入：10
输出：4 4

输入：100
输出：25 25

输入：1000
输出：168 168

输入：10000
输出：1229 1229

可以看出，埃氏筛法的效率比暴力枚举法高很多。