欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-03-13 09:51:41
...

题目描述

请考虑性能

输入描述:

一个整数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;
}

思路:无。