当前位置: 首页 > news >正文

算法练习(八)计数质数(素数)

1、问题描述: 给定整数 n ,返回 所有小于非负整数 n 的质数的数量 。

2、示例如下:
在这里插入图片描述
3、代码如下:

第一种:比较暴力的算法

class Solution {public int countPrimes(int n) {int count=1;if(n<=2) return 0;for(int i=3;i<n;i+=2){boolean isPrime=true;for(int j=3;j<=Math.sqrt(i);j+=2){	//一一排除if(i%j==0)isPrime=false;}if(isPrime)count++;}return count;}
}

第二种:埃氏筛

class Solution {public int countPrimes(int n) {int[] isPrime = new int[n];Arrays.fill(isPrime, 1);	//初始填充int ans = 0;for (int i = 2; i < n; ++i) {if (isPrime[i] == 1) {	//等于1表示是质数ans += 1;if ((long) i * i < n) {for (int j = i * i; j < n; j += i) {	//把小于n的从2开始的各种质数的倍数标0,当遍历完成后,数量也就出来了isPrime[j] = 0;		}}}}return ans;}
}

第三种:线性筛(核心原理是在埃氏筛的基础上不重复标记)

class Solution {public int countPrimes(int n) {List<Integer> primes = new ArrayList<Integer>();int[] isPrime = new int[n];Arrays.fill(isPrime, 1);for (int i = 2; i < n; ++i) {if (isPrime[i] == 1) {primes.add(i);}for (int j = 0; j < primes.size() && i * primes.get(j) < n; ++j) {isPrime[i * primes.get(j)] = 0;if (i % primes.get(j) == 0) {break;}}}return primes.size();}
}

相关文章:

算法练习(八)计数质数(素数)

1、问题描述&#xff1a; 给定整数 n &#xff0c;返回 所有小于非负整数 n 的质数的数量 。 2、示例如下&#xff1a; 3、代码如下&#xff1a; 第一种&#xff1a;比较暴力的算法 class Solution {public int countPrimes(int n) {int count1;if(n<2) return 0;for(in…...

用反射模拟IOC模拟getBean

IOC就是spring的核心思想之一&#xff1a;控制反转。这里不再赘述&#xff0c;看我的文章即可了解&#xff1a;spring基础思想IOC其次就是java的反射&#xff0c;反射机制是spring的重要实现核心&#xff0c;今天我看spring的三级缓存解决循坏引用的问题时&#xff0c;发现一个…...

【Ap AutoSAR入门与实战开发02】-【Ap_s2s模块01】: s2s的背景

总目录链接==>> AutoSAR入门和实战系列总目录 文章目录 1 s2s的背景?2 AUTOSAR 方法应支持车辆的无缝开发2.1 面向服务的ECU的解读2.2 面向信号的ECU的解读2.3 通过网关ECU实现转换1 s2s的背景? Cp AutoSAR基于传统的can,lin,flexray总线的通信,一般是面向信号设…...

C语言数据结构(3)----无头单向非循环链表

目录 1. 链表的概念及结构 2. 链表的分类 3. 无头单向非循环链表的实现(下面称为单链表) 3.1 SListNode* BuySListNode(SLTDateType x) 的实现 3.2 void SListPrint(SListNode* plist) 的实现 3.3 void SListPushBack(SListNode** pplist, SLTDateType x) 的实现 3.4 voi…...

Android 实现菜单拖拽排序

效果图简介本文主角是ItemTouchHelper。它是RecyclerView对于item交互处理的一个「辅助类」&#xff0c;主要用于拖拽以及滑动处理。以接口实现的方式&#xff0c;达到配置简单、逻辑解耦、职责分明的效果&#xff0c;并且支持所有的布局方式。功能拆解功能实现4.1、实现接口自…...

通过window.open打开新的页面并修改样式添加内容

const img new Image(); img.src res; //res是图片的路径地址 const newWin window.open(, _blank); newWin.document.write(img.outerHTML); // newWin.document.body.style.background #000; newWin.document.body.style.textAlign center; newWin.document.body.oncl…...

Java中 Synchronized 的用法

《编程思想之多线程与多进程(1)——以操作系统的角度述说线程与进程》一文详细讲述了线程、进程的关系及在操作系统中的表现&#xff0c;这是多线程学习必须了解的基础。本文将接着讲一下Java线程同步中的一个重要的概念synchronized. synchronized是Java中的关键字&#xff0c…...

Rust语言的基本介绍

rust缘起和目标 rust的英文是锈菌&#xff0c;是一种真菌&#xff0c;这种真菌的生命力非常顽强&#xff0c;其 在生命周期内可以产生多达5种孢子类型&#xff0c;这5种生命形态还可以相互转 化。“Rust”也有“铁锈”的意思&#xff0c;暗合“裸金属”之意&#xff0c;代表了R…...

新冠小阳人症状记录

原想挺过春节后再养&#xff0c;发现事与愿违。生理期期间抵抗力下降&#xff0c;所以在生理期第二天就有些症状了。可能是生理期前一天出去采购食物染上&#xff0c;也可能是合租夫妻染上。anyway&#xff0c;记录下自己的症状与相应有效的偏方&#xff1a; 第一天&#xff1a…...

SQL零基础入门学习(十四)

上篇&#xff1a;SQL零基础入门学习&#xff08;十三&#xff09; SQL NULL 值 NULL 值代表遗漏的未知数据。 默认地&#xff0c;表的列可以存放 NULL 值。 如果表中的某个列是可选的&#xff0c;那么我们可以在不向该列添加值的情况下插入新记录或更新已有的记录。这意味着该…...

Excel工作表不能移动或复制?看看是不是这两个原因

Excel工作表不能移动或复制&#xff1f;今天来看看如何解决。 大家都知道&#xff0c;Excel表格分为工作簿和工作表&#xff0c;工作簿就是整个Excel文件&#xff1b;工作簿里面&#xff0c;也就是Excel表可以有多个工作表。 而各个工作表之间是可以相互移动或复制的&#xf…...

利用递归实现括号匹配

案例引入以下则是各个字符串经过括号处理之后的结果&#xff1a;12((21))(12-->12(21)1232((((2121)212(21)-->32(2121)212(21)ABDF((SA)SA)SA(SA)SA(((-->ABDF((SA)SA)SA(SA)SA算法思路&#xff1a;这个问题的解决方法就是将字符按顺序逐一加入到新的string容器store…...

14.线程数量怎么制定?

什么是CPU 密集型任务和耗时 IO 型任务 &#xff1f; CPU 密集型任务 CPU 密集型任务&#xff0c;比如加密、解密、压缩、计算等一系列需要大量耗费 CPU 资源的任务。 耗时 IO 型任务 数据库、文件的读写&#xff0c;网络通信等任务&#xff0c;这种任务的特点是并不会特别消耗…...

C++中STL标准模板库学习记录

文章目录&#xff1a;1.vector1.1 遍历方式1.2 构造函数1.3 容量大小问题1.4 插入和删除1.5 存取值1.6 交换两个vectot的元素1.7 预定义存储空间2.string3. deque4. stack4.1 常用函数5. queue5.1 特点5.2 方法6. list6.1 优点6.2 缺点6.3 构造函数6.4 交换6.5 大小6.6 插入和删…...

《数据库系统概论》学习笔记——第六章 关系数据理论

教材为数据库系统概论第五版&#xff08;王珊&#xff09; 这一章重点在于各种范式的概念和将低级范式转为高级范式。一定要看多值依赖和4NF&#xff08;因为这个概念很绕又烦&#xff0c;但是期中期末都考了&#xff09;。最后计算题就是一定要会&#xff1a;算闭包&#xff0…...

Odoo | Webserivce | 5分钟学会【JSONRPC】接口开发

文章目录Odoo - JsonRPC1. Odoo内方法结构&#xff08;接收端&#xff09;2. POST接口请求结构&#xff08;发送端&#xff09;3. 实例测试Odoo - JsonRPC 1. Odoo内方法结构&#xff08;接收端&#xff09; # -*- coding: utf-8 -*- import odoo import logging import trac…...

搜广推 NeuralCF - 改进协同过滤+矩阵分解的思想

😄 NeuralCF:2017新加坡国立大学提出。【后文简称NCF】 😄 PNN:2016年上海交通大学提出。 文章目录 NeuralCF动机原理general NCFNCF终极版(GMF+MLP的结合)缺点优点ReferenceNeuralCF 动机 前面学了MF,可知MF在用户-物品评分矩阵的基础上做矩阵分解(用户矩阵Q和物品…...

dbever连接kerberos认证的hive

文章目录一、本地安装kerberos客户端二、本地kerberos客户端登录三、dbever连接hive一、本地安装kerberos客户端 下载地址&#xff1a;https://web.mit.edu/kerberos/dist/index.html 安装&#xff1a;下一步或者自定义安装即可 安装后会自动生成配置文件&#xff1a;C:\Pro…...

pom依赖产生的各种问题

文章目录问题一(org.apache.ibatis.session.Configuration)解决方法问题二(ERROR StatusLogger No log4j2)解决方法问题三(com.google.common.util.concurrent)解决方法问题四(start bean documentationPluginsBootstrapper)解决方法问题五(Unable to infer base url. )解决办法…...

RPC编程:RPC框架设计目标

一&#xff1a;前导知识 Http是超文本传输协议&#xff0c;跨平台性非常好。Http可以传输文本&#xff0c;更多的时候传输的是文本&#xff0c;我们也是可以传输二进制的&#xff0c;我们基于Http进行下载的时候&#xff0c;就是走的Http协议。 Tcp协议&#xff0c;处理的时候…...

如何突破窗口限制:3分钟掌握WindowResizer强制调整技巧

如何突破窗口限制&#xff1a;3分钟掌握WindowResizer强制调整技巧 【免费下载链接】WindowResizer 一个可以强制调整应用程序窗口大小的工具 项目地址: https://gitcode.com/gh_mirrors/wi/WindowResizer 还在为那些无法拖拽大小的应用程序窗口而烦恼吗&#xff1f;Win…...

Dify实战指南:从零构建大模型应用与智能体开发全流程

1. 项目概述&#xff1a;从零到一&#xff0c;构建你的大模型应用开发实战手册如果你对AI应用开发感兴趣&#xff0c;但又觉得从零开始搭建一个能用的智能体&#xff08;Agent&#xff09;或者知识库问答系统门槛太高&#xff0c;那么你很可能已经听说过Dify这个名字。作为一个…...

群晖NAS进阶指南:借助Docker容器部署全能DDNS服务,实现多平台域名与公网IP智能同步

1. 为什么需要全能DDNS服务&#xff1f; 家里有群晖NAS的朋友可能都遇到过这样的烦恼&#xff1a;明明设置了外网访问&#xff0c;但过几天就失效了。这是因为大多数家庭宽带分配的都是动态公网IP&#xff0c;运营商会定期更换你的IP地址。想象一下&#xff0c;这就像你的手机…...

基于Python与aiogram构建多模型AI助手:集成GPT-4、Claude与Gemini的Telegram机器人开发实践

1. 项目概述&#xff1a;一个多模型AI助手的自研之路 最近在折腾一个挺有意思的玩意儿&#xff0c;我把它叫做“AIAssistantBot”。简单来说&#xff0c;这是一个跑在Telegram上的机器人&#xff0c;但它不是那种只会回复固定指令的“傻”机器人。它的核心是整合了市面上几家主…...

Robodyssey机器人教育:从STEM理念到项目实践,点燃孩子科技兴趣

1. 项目概述与核心理念十年前&#xff0c;我在一次行业展会上第一次看到一群孩子围着一个摊位&#xff0c;他们不是在玩现成的玩具&#xff0c;而是聚精会神地调试着自己手里那些由电线、电路板和塑料零件组成的“小怪物”。那个摊位就是Robodyssey。当时我就在想&#xff0c;把…...

如何快速破解Cursor Pro限制:一键激活AI编程助手的完整指南

如何快速破解Cursor Pro限制&#xff1a;一键激活AI编程助手的完整指南 【免费下载链接】cursor-free-vip [Support 0.45]&#xff08;Multi Language 多语言&#xff09;自动注册 Cursor Ai &#xff0c;自动重置机器ID &#xff0c; 免费升级使用Pro 功能: Youve reached you…...

实战部署Funannotate基因组注释工具:3种高效配置方案指南

实战部署Funannotate基因组注释工具&#xff1a;3种高效配置方案指南 【免费下载链接】funannotate Eukaryotic Genome Annotation Pipeline 项目地址: https://gitcode.com/gh_mirrors/fu/funannotate Funannotate是一款专业的真核生物基因组注释工具&#xff0c;特别针…...

长裕集团上交所上市:大涨562%市值375亿 年营收18亿净利2.6亿

雷递网 雷建平 5月11日 长裕控股集团股份有限公司&#xff08;简称&#xff1a;“长裕集团”&#xff0c;股票代码&#xff1a;“603407”&#xff09;今日在上交所主板上市。长裕集团发行价为13.86元&#xff0c;发行4100万股&#xff0c;募资总额为5.68亿元。长裕集团今日开盘…...

如何轻松掌握开源OCR插件的实用技巧:5步快速上手指南

如何轻松掌握开源OCR插件的实用技巧&#xff1a;5步快速上手指南 【免费下载链接】Umi-OCR_plugins Umi-OCR 插件库 项目地址: https://gitcode.com/gh_mirrors/um/Umi-OCR_plugins 你是否曾被纸质文档的数字化问题困扰&#xff1f;或者需要从图片中提取数学公式却找不到…...

从零构建Telegram天气机器人:Python异步编程与API集成实战

1. 项目概述&#xff1a;一个能聊天的天气机器人 如果你用过Telegram&#xff0c;大概率会见过或者用过一些机器人。它们能帮你查新闻、翻译、管理任务&#xff0c;甚至陪你聊天。今天要聊的这个项目&#xff0c; imkarimkarim/Telegram-Weather-Bot &#xff0c;就是一个典型…...