返回小于 N 的质数个数 C++解法

题目描述

请考虑性能

输入描述:

一个整数N

输出描述:

小于N的质数数量

示例1

输入
10
输出
4

说明

N=10，质数有 [2, 3, 5, 7]

#include <bits/stdc++.h>

using namespace std;

bool isPrime(int n)   //判断一个数是否为质数
{
	if (n <= 1) return false;
	else
	{
		for (int i = 2; i <= sqrt(n); i++) if (n % i == 0) return false;
		return true;
	}
}
void main()
{
	int n;
	cin >> n;
	int cnt = 0;
	for (int i = 1; i < n; ++i)
	{
		if (isPrime(i)) cnt++;
	}
	cout << cnt << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

思路：无。