返回小于N的质数个数

var dd = “hello”;
dnqoindq

题目链接：返回小于 N 的质数个数_牛客题霸_牛客网 (nowcoder.com)

题目描述：

返回小于 N 的质数个数

示例：
输入：10
输出：4
说明：N=10，质数有 [2, 3, 5, 7]

💡

📖流程描述：
质数只能被1和自身整除的数

1. 遍历判断是否为质数；
2. 判断质数（优化：0、1和偶数不是质数）跳过偶数；

⌨️代码实现：

#include <iostream>
using namespace std;

// 2. 判断质数
int is_prime(int x)
{
	if (x == 0 || x == 1) return 0;    //2.1 0和1不是质数
	if (x == 2) return 1;   //2.2 2是质数
	if (x % 2 == 0) return 0;    //2.3 除2外偶数不是质数
	int i = 3; 
	for (; i * i <= x; i += 2)    //2.3 跳过偶数
		if (x % i == 0) return 0;
	return 1;
}

int main()
{
	int n = 0;
	while (cin >> n)
	{
		int count = 0;
		//1. 遍历判断
		while (n > 1)
			if (is_prime(n--)) ++count;
		cout << count << endl;
	}
	return 0;
}

运行结果：