当前位置: 首页 > 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问…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

oracle与MySQL数据库之间数据同步的技术要点

Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异&#xff0c;它们的数据同步要求既要保持数据的准确性和一致性&#xff0c;又要处理好性能问题。以下是一些主要的技术要点&#xff1a; 数据结构差异 数据类型差异&#xff…...

Java多线程实现之Callable接口深度解析

Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...