当前位置:网站首页>leetcode 204. Count Primes 计数质数 (Easy)
leetcode 204. Count Primes 计数质数 (Easy)
2022-08-01 21:46:00 【InfoQ】
一、题目大意
- 0 <= n <= 5 * 106
二、解题思路
三、解题方法
3.1 Java实现
public class Solution {
public int countPrimes(int n) {
if (n <= 2) {
return 0;
}
boolean[] prime = new boolean[n];
Arrays.fill(prime, true);
int i = 3;
int sqrtn = (int) Math.sqrt(n);
// 偶数一定不是质数
int count = n / 2;
while (i <= sqrtn) {
// 最小质因子一定小于等于开方数
for (int j = i * i; j < n; j += 2 * i) {
// 避免偶数和重复遍历
if (prime[j]) {
count--;
prime[j] = false;
}
}
do {
i+= 2;
// 避免偶数和重复遍历
} while (i <= sqrtn && !prime[i]);
}
return count;
}
}
四、总结小记
- 2022/8/1 7月结束了贪心算法的题,开启“巧解数学问题”类的题目
边栏推荐
- C Expert Programming Chapter 1 C: Through the Fog of Time and Space 1.3 The Standard I/O Library and the C Preprocessor
- ModuleNotFoundError: No module named ‘yaml‘
- 虚拟内存与物理内存之间的关系
- 微软校园大使喊你来秋招啦!
- Shell编程条件语句
- Unity Shader 常规光照模型代码整理
- Centos7--MySQL的安装
- 365天挑战LeetCode1000题——Day 046 生成每种字符都是奇数个的字符串 + 两数相加 + 有效的括号
- Chapter 12, target recognition of digital image processing
- Spark practice questions + answers
猜你喜欢
HCIP---Multiple Spanning Tree Protocol related knowledge points
SQL injection of WEB penetration
ARFoundation Getting Started Tutorial U2-AR Scene Screenshot Screenshot
Based on php hotel online reservation management system acquisition (php graduation project)
递归(各经典例题分析)
Image fusion GANMcC study notes
数字图像处理 第十二章——目标识别
AI应用第一课:支付宝刷脸登录
JVM内存结构详解
基于php影视资讯网站管理系统获取(php毕业设计)
随机推荐
Uses of Anacoda
上传markdown文档到博客园
Shell编程之条件语句
C Pitfalls and Defects Chapter 7 Portability Defects 7.8 Size of Random Numbers
SAP ABAP OData 服务如何支持删除(Delete)操作试读版
SOM网络2: 代码的实现
方舟:生存进化官服和私服区别
Anacoda的用途
Mini Program--Independent Subcontracting & Subcontracting Pre-download
方舟:生存进化PVE模式和PVP模式
方舟开服需要知道的那些事
迁移学习——Discriminative Transfer Subspace Learning via Low-Rank and Sparse Representation
数据库练习
Transformer学习
【C语言】猜数字小游戏
你居然不懂Bitmap和Drawable? 相关知识大扫盲
Shell programming conditional statement
【力扣】字符串相乘
Scala练习题+答案
Based on php film and television information website management system acquisition (php graduation design)