习题：计数质数（C语言）

题目

统计所有小于非负整数 n 的质数的数量。

示例 1：

输入：n = 10

输出：4

解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

示例 2：

输入：n = 0

输出：0

示例 3：

输入：n = 1

输出：0

提示：

0 <= n <= 5 * 106

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-primes

暴力法，在5000000超时

int countPrimes(int n)
{
	if (n <= 2)   return 0;
	int count = 0;
	for (int i = 1; i < n; i += 2)
	{
		int flag = 0;
		for (int j = 2; j <= sqrt(i); j++)
		{
			if (i % j == 0)
			{
				flag = 1;
				break;
			}
		}
		if (flag == 0)
			count++;
	}
	return count;
}

方法二：埃氏筛
要得到自然数n以内的全部素数，必须把小于等于sqrt(n)的所有素数的倍数剔除，剩下的就是素数。
给出要筛数值的范围n，找出以内的素数。

• 先用2去筛，即把2留下，把2的倍数剔除掉；
• 再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉；
• 接下去用下一个质数5筛，把5留下，把5的倍数剔除掉；
• 不断重复下去…。

int countPrimes(int n)
{
	if (n < 2)
		return 0;
	int* a = (int*)calloc(n+1,sizeof(int));
	int count = 0;
	for (int i = 2; i < n; i++)
	{
		if (a[i] == 0)//第一个2肯定为质数
		{
			count++;
			for (int j = 2 * i; j < n; j += i)//除了质数本身之外，他的倍数都是合数
			{
				a[j] = 1;//将合数置为1
			}
		}
	}
	return count;
}