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

算法通关村——数论经典问题解析

1. 辗转相除法

主要目的是获取两个数里面的最大公约数。

 public int gcd(int a, int b) {int k = 0;do {k = a % b;a = b;b = k;} while (k != 0);return a;}

2. 素数和合数

素数的要求是必须大于等于2,并且只能被1和它本身整除。

判断的方法比较简单,就是从2开始到n一直相除,判断是否等于0。但是其实可以不需要判断到n,到根号n即可。

    public boolean isPrim(int num) {for (int i = 2; i <= Math.sqrt(num); i++) {if (num % i == 0) {return false;}}return true;}

2.1 计数质数

计数质数
给定整数 n ,返回 所有小于非负整数 n 的质数的数量 。
示例 1:
输入:n = 10
输出:4
解释:小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2:

输入:n = 0
输出:0
示例 3:

输入:n = 1
输出:0

2.2 枚举法

质数的定义:除了1和它本身,没有其余的因数。而这道题目是用来同一某个元素内出现质数的个数,只需要再添加一个循环,用于判断每个数是否是质数,是就加一,而判断方法就是上面的方法。

    public int countPrimes(int n) {int count =0;for(int i=2;i<n;i++){if(isPrim(i)){count ++;}}return count;}public boolean isPrim(int n){for(int i=2;i<=Math.sqrt(n);i++){if(n % i == 0){return false;}}return true;}

不过这样写是力扣测试通过不了,效率太低。

3. 埃氏筛

定义:如果 xxx 是质数,那么大于 xxx 的 xxx 的倍数 2x,3x,…2x,3x,\ldots2x,3x,… 一定不是质数,因此我们可以从这里入手。
例如 2是素数,那么2的倍数一定不是素数,3也是同理,只需要使用一个标记是不是质数,是质数就标记为1,将不是质数的标记为0。

public int countPrimes(int n) {int [] isPrim = new int [n];int ans = 0;Arrays.fill(isPrim,1);for(int i =2;i<n;i++){if(isPrim[i] == 1){ans+=1;if(i*i<n){for(int j=i;j<n;j+=i){isPrim[j] = 0;}}}}return ans;
}

4. 丑数

定义:因数只包含2,3,5。当 n>0 时,若 n 是丑数,则 n 可以写成 n = 2 ^ a + 3 ^ b + 5 ^ c 的形式,其中 a,b,c 都是非负整数。特别地,当 a,b,c 都是 000 时,n=1。

4.1 丑数

丑数
丑数 就是只包含质因数 2、3 和 5 的正整数。
给你一个整数 n ,请你判断 n 是否为 丑数 。如果是,返回 true ;否则,返回 false 。

示例 1:

输入:n = 6
输出:true
解释:6 = 2 × 3
示例 2:

输入:n = 1
输出:true
解释:1 没有质因数,因此它的全部质因数是 {2, 3, 5} 的空集。习惯上将其视作第一个丑数。
示例 3:

输入:n = 14
输出:false
解释:14 不是丑数,因为它包含了另外一个质因数 7 。

4.2 数学法

 public boolean isUgly(int n) {if(n<=0) return false;int [] factors = {2,3,5};for(int factor:factors){while(n % factor == 0){n /= factor;}}return  n==1;}

相关文章:

算法通关村——数论经典问题解析

1. 辗转相除法 主要目的是获取两个数里面的最大公约数。 public int gcd(int a, int b) {int k 0;do {k a % b;a b;b k;} while (k ! 0);return a;}2. 素数和合数 素数的要求是必须大于等于2&#xff0c;并且只能被1和它本身整除。 判断的方法比较简单&#xff0c;就是从…...

代码随想录算法训练营第四十六天|LeetCode 1143,1035,53

目录 LeetCode 1143.最长公共子序列 动态规划五步曲&#xff1a; 1.确定dp[i][j]的含义 2.找出递推公式 3.初始化dp数组 4.确定遍历顺序 5.打印dp数组 LeetCode 1035.不相交的线 LeetCode 53.最大子序列和&#xff08;动态规划&#xff09; 动态规划五步曲&#xff1a; 1.确定…...

leetcode 541.反转字符串II

⭐️ 题目描述 &#x1f31f; leetcode链接&#xff1a;https://leetcode.cn/problems/reverse-string-ii/ ps&#xff1a; 这道题描述的有点晦涩难懂&#xff0c;意思就是每隔k个反转k个&#xff0c;末尾不够k个时全部反转&#xff0c;开始就不够k个也全部反转。 代码&#…...

MyBatis与Spring整合以及AOP和PageHelper分页插件整合

目录 前言 一、MyBatis与Spring整合的好处以及两者之间的关系 1.好处 2.关系 二、MyBatis和Spring集成 1.导入pom.xml 2.编写配置文件 3.利用mybatis逆向工程生成模型层代码 三、常用注解 四、AOP整合pageHelper分页插件 创建一个切面 测试 前言 MyBatis是一个开源的…...

《认知觉醒》读书笔记之潜意识

模糊--人生是一场消除模糊的比赛。 学习知识&#xff0c;消除认知模糊 掌握的工具越多&#xff0c;认知能力越强&#xff0c;消除模糊的能力就越强。 元认知-----》 如何反观自己。 刻意练习----》 如何精进自己。 运动改造大脑---》 如何激化自己的运动热情。 学习知识的…...

Stable Diffusion 系列教程 | 图生图基础

前段时间有一个风靡全网的真人转漫画风格&#xff0c;受到了大家的喜欢 而在SD里&#xff0c;就可以通过图生图来实现类似的效果 当然图生图还有更好玩的应用&#xff0c;我们一点一点来探索 首先我们来简单进行一下图生图的这一个实践---真人转动漫 1. 图生图基本界面 和…...

cuda编程day001

一、环境&#xff1a; ①、linux cuda-11.3 opecv4.8.0 不知道头文件和库文件路径&#xff0c;用命令查找&#xff1a; # find /usr/local -name cuda.h 2>/dev/null # 查询cuda头文件路径 /usr/local/cuda-11.3/targets/x86_64-linux/include/cuda.h # find /usr/…...

Java 中使用 ES 高级客户端库 RestHighLevelClient 清理百万级规模历史数据

&#x1f389;工作中遇到这样一个需求场景&#xff1a;由于ES数据库中历史数据过多&#xff0c;占用太多的磁盘空间&#xff0c;需要定期地进行清理&#xff0c;在一定程度上可以释放磁盘空间&#xff0c;减轻磁盘空间压力。 &#x1f388;在经过调研之后发现&#xff0c;某服务…...

C++最易读手撸神经网络两隐藏层(任意Nodes每层)梯度下降230821a

// c神经网络手撸20梯度下降22_230820a.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 #include<iostream> #include<vector> #include<iomanip> // setprecision #include<sstream> // getline stof() #include<fstream…...

Leetcode 2235.两整数相加

一、两整数相加 给你两个整数 num1 和 num2&#xff0c;返回这两个整数的和。 示例 1&#xff1a; 输入&#xff1a;num1 12, num2 5 输出&#xff1a;17 解释&#xff1a;num1 是 12&#xff0c;num2 是 5 &#xff0c;它们的和是 12 5 17 &#xff0c;因此返回 17 。示例…...

Postman —— postman实现参数化

什么时候会用到参数化 比如&#xff1a;一个模块要用多组不同数据进行测试 验证业务的正确性 Login模块&#xff1a;正确的用户名&#xff0c;密码 成功&#xff1b;错误的用户名&#xff0c;正确的密码 失败 postman实现参数化 在实际的接口测试中&#xff0c;部分参数每…...

LeetCode--HOT100题(41)

目录 题目描述&#xff1a;102. 二叉树的层序遍历&#xff08;中等&#xff09;题目接口解题思路代码 PS: 题目描述&#xff1a;102. 二叉树的层序遍历&#xff08;中等&#xff09; 给你二叉树的根节点 root &#xff0c;返回其节点值的 层序遍历 。 &#xff08;即逐层地&am…...

微信小程序教学系列(6)

第六章&#xff1a;小程序商业化 第一节&#xff1a;小程序的商业模式 在这一节中&#xff0c;我们将探讨微信小程序的商业模式&#xff0c;让你了解如何将你的小程序变成一个赚钱的机器&#xff01; 1. 广告收入 小程序的商业模式之一是通过广告收入赚钱。你可以在小程序中…...

小程序中的全局配置以及常用的配置项(window,tabBar)

全局配置文件和常用的配置项 app.json: pages:是一个数组&#xff0c;用于记录当前小程序所有页面的存放路径&#xff0c;可以通过它来创建页面 window:全局设置小程序窗口的外观(导航栏&#xff0c;背景&#xff0c;页面的主体) tabBar:设置小程序底部的 tabBar效果 style:是否…...

数据工厂调研及结果展示

数据工厂 一、背景 在开发自测、测试迭代测试、产品验收的过程中&#xff0c;都需要各种各样的前置数据&#xff0c;大致分为如下几类&#xff1a; 账号&#xff08;实名、权益等级、注册等&#xff09; 货源&#xff08;优货、急走、相似、一手、普通货源等&#xff09; …...

抓包相关,抓包学习

检查网络流量 - 提琴手经典 (telerik.com) Headers Reference - Fiddler Classic (telerik.com) 以上是fiddler官方文档 F12要勾选保留日志 不勾选的话跳转到新页面之前页面的日志不会在下方显示 会保留所有抓到的包 如果重定向到别的页面 F12抓包可能看不到响应信息,但是…...

云原生之使用Docker部署SSCMS内容管理系统

云原生之使用Docker部署SSCMS内容管理系统 一、SSCMS介绍二、本地环境介绍2.1 本地环境规划2.2 本次实践介绍 三、本地环境检查3.1 检查Docker服务状态3.2 检查Docker版本3.3 检查docker compose 版本 四、下载SSCMS镜像五、部署SSCMS内容管理系统5.1 创建SSCMS容器5.2 检查SSC…...

uniapp -- 在组件中拿到pages.json下pages设置navigationBarTitleText这个值?

1:在 pages.json 文件中设置 navigationBarTitleText,例如: {"pages": [{"path": "pages/home/index","style": {"navigationBarTitleText": "首页",&...

Java获取环境变量和运行时环境信息和自定义配置信息

System.getenv() 获取系统环境变量 public static void main1() {Map<String, String> envMap System.getenv();envMap.entrySet().forEach(x-> System.out.println(x.getKey() "" x.getValue())); } System.getenv() 获取的是操作系统环境变量列表&…...

React入门 组件学习笔记

项目页面以组件形式层层搭起来&#xff0c;组件提高复用性&#xff0c;可维护性 目录 一、函数组件 二、类组件 三、 组件的事件绑定 四、获取事件对象 五、事件绑定传递额外参数 六、组件状态 初始化状态 读取状态 修改状态 七、组件-状态修改counter案例 八、this问…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...