首页 > 试题广场 >

返回小于 N 的质数个数

[编程题]返回小于 N 的质数个数
  • 热度指数：5290 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
请考虑性能

输入描述:
一个整数N


输出描述:
小于N的质数数量
示例1

输入

10

输出

4

说明

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

备注:
0、1 不属于质数。
算法知识视频讲解
开通博客
头像 罅隙·
发表于 2022-07-10 17:19:29
一、原式版本 bool is_prime(int n) { for(int i = 2; i < n; i++) { if(n % i == 0) return false; } return true; } int m 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 白伟仝
发表于 2020-07-24 22:05:57
暴力遍历判断质数即可： import java.util.*; public class Main { public static void main(String[] args) throws Exception{ Scanner sc = new Scanner(Syst 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛客12138451号
发表于 2023-07-03 10:17:24
#include <iostream> using namespace std; bool isPrime(int n){ for(int i=2;i<n;i++){//如果n被i整除，则返回false if(n%i==0){ re 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 重生之我要当分子
发表于 2025-01-07 22:39:22
解题思路 使用埃氏筛法（Eratosthenes筛法）计算质数： 创建标记数组 从2开始标记所有合数 优化筛选范围到sqrt(n) 关键点 使用位运算优化空间 只需标记到sqrt(n) 跳过偶数优化 代码 cpp java python #include <iostr 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 bao_hu_yuan_zhang
发表于 2024-03-21 20:59:57
#include <iostream> using namespace std; bool isprime(int n) { int i=0; if(n==2) { return 1; } else { 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 道衍丶
发表于 2022-12-25 21:02:37
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <string.h> int main() { int n = 0,cnt = 0; scanf( 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 穷举 算法工程师 摩拜 2018 PHP工程师 数学 Java工程师
来自：摩拜2018校招客户端...
上传者：小小
难度：
26条回答 8082浏览

热门推荐

通过挑战的用户

查看代码

相关试题

返回小于 N 的质数个数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号