当前位置:网站首页>【刷题篇】计算质数
【刷题篇】计算质数
2022-07-30 18:50:00 【m0_60631323】
一、题目
OJ链接
给定整数 n ,返回 所有小于非负整数 n 的质数的数量 .
二、题解
思路:将1~n-1上不是素数的数全部除去,剩下的数的数量就是素数
- 除了2,所有的偶数都不是素数,因为4=2x2;6=2x3;8=2x4…
- 在去除掉因子中含有3的所有不是素数的数,
3x2不用再算了,因为计算2x3的时候算过了,所以对于数字i只需从 i x i 开始,3x3=9(不是素数), 3x4不用算(偶数),3x5=15(不是素数)…
public int countPrimes1(int n) {
if(n<3){
return 0;
}
boolean[] f=new boolean[n];
int count =n/2;
for(int i=3;i*i<n;i+=2){
if(f[i]){
//例如i=9时,9在3*3的时候就判断过9不是素数,就已经
//将f[9]=true,而之所以可以跳过9是因为,9*9=3*3*9,
//9*11=3*3*11,就说明,含有9这个因子且不是素数的数,在
//去除以3作为因子所有不是素数的数的时候已经算过了
continue;
}
for(int j=i*i;j<n;j+=2*i){
if(!f[j]){
count--;
f[j]=true;
}
}
}
return count;
}
边栏推荐
- kotlin by lazy
- AWS console
- 开心的聚餐
- WEBSOCKETPP使用简介+demo
- Go 系统收集
- [OC study notes] attribute keyword
- Quickly build an e-commerce platform based on Amazon cloud technology serverless service - performance
- CIMC Shilian Dafeitong is the global industrial artificial intelligence AI leader, the world's top AI core technology, high generalization, high robustness, sparse sample continuous learning, industri
- One year after graduation, I was engaged in software testing and won 11.5k. I didn't lose face to the post-98 generation...
- Multiple instances of mysql
猜你喜欢
"Ruffian Heng Embedded Bimonthly" Issue 59
一文读懂“语言模型”
卫星电话是直接与卫星通信还是通过地面站?
The Meta metaverse division lost 2.8 billion in the second quarter!Still want to keep betting?Metaverse development has yet to see a way out!
After 23 years of operation, the former "China's largest e-commerce website" has turned yellow...
NC | Tao Liang Group of West Lake University - TMPRSS2 "assists" virus infection and mediates the host invasion of Clostridium sothrix hemorrhagic toxin...
微信小程序云开发 | 城市信息管理
ByteArrayInputStream class source code analysis
Critical Reviews | A review of the global distribution of antibiotics and resistance genes in farmland soil by Nannong Zou Jianwen's group
【Swords Offer】Swords Offer 17. Print n digits from 1 to the largest
随机推荐
还有三天忙完
【Pointing to Offer】Pointing to Offer 18. Delete the node of the linked list
6块钱1斤,日本公司为何来中国收烟头?
延时队列优化 (2)
[OC study notes] attribute keyword
Application of time series database in the field of ship risk management
MYSQL(基本篇)——一篇文章带你走进MYSQL的奇妙世界
智慧中控屏
开心的聚餐
【剑指 Offe】剑指 Offer 17. 打印从1到最大的n位数
OneFlow source code analysis: Op, Kernel and interpreter
WeChat Mini Program Cloud Development | Urban Information Management
MySQL——基础知识
国轩高科瑞交所上市:募资近7亿美元 为瑞士今年最大融资项目
Quickly build an e-commerce platform based on Amazon cloud technology serverless service - performance
微博广告分布式配置中心的构建与实践(有彩蛋)
Critical Reviews | 南农邹建文组综述全球农田土壤抗生素与耐药基因分布
设计消息队列存储消息数据的 MySQL 表格
网络基础(二)-Web服务器-简介——WampServer集成服务器软件之Apache+MySQL软件安装流程 & netstat -an之检测计算机的端口是否占用
[Prometheus] An optimization record of the Prometheus federation [continued]