204. 计数质数 (埃式筛法详解)——【Leetcode每日一题】

素数最朴素判断思路:(一般会超时)

对正整数 n,如果用 2 到 n \sqrt{n} n 之间的所有整数去除,均无法整除,则 n 为素数又称为质数。

为什么到 n \sqrt{n} n 就可以了,因为因数如果存在一定是成对出现的,如果存在小于根号n的因数,那么n除以它一定大于根号n。

首先要先知道以下几个知识点:

1、素数分解

  • 每一个数 都可以分解成 素数的乘积,且这种分解是唯一的,例如: 84 = 2 2 ∗ 3 1 ∗ 5 0 ∗ 7 1 ∗ 1 1 0 ∗ 1 3 0 ∗ 1 7 0 ∗ … 84 = 2^2 * 3^1 * 5^0 * 7^1 * 11^0 * 13^0 * 17^0 * … 84=22315071110130170

2、整除

  • x = 2 m 0 ∗ 3 m 1 ∗ 5 m 2 ∗ 7 m 3 ∗ 1 1 m 4 ∗ … x = 2^{m0} * 3^{m1} * 5^{m2} * 7^{m3} * 11^{m4} * … x=2m03m15m27m311m4
  • y = 2 n 0 ∗ 3 n 1 ∗ 5 n 2 ∗ 7 n 3 ∗ 1 1 n 4 ∗ … y = 2^{n0} * 3^{n1} * 5^{n2} * 7^{n3} * 11^{n4} * … y=2n03n15n27n311n4

如果 x x x 整除 y y y y y y mod x x x == 0),则对于所有 i i i m i < = n i m^i <= n^i mi<=ni

3、最大公约数最小公倍数

  • x x x y y y最大公约数为: g c d ( x , y ) = 2 m i n ( m 0 , n 0 ) ∗ 3 m i n ( m 1 , n 1 ) ∗ 5 m i n ( m 2 , n 2 ) ∗ . . . gcd(x,y) = 2^{min(m0,n0)} * 3^{min(m1,n1)} * 5^{min(m2,n2)} * ... gcd(x,y)=2min(m0,n0)3min(m1,n1)5min(m2,n2)...

  • x x x y y y最小公倍数为: l c m ( x , y ) = 2 m a x ( m 0 , n 0 ) ∗ 3 m a x ( m 1 , n 1 ) ∗ 5 m a x ( m 2 , n 2 ) ∗ . . . lcm(x,y) = 2^{max(m0,n0)} * 3^{max(m1,n1)} * 5^{max(m2,n2)} * ... lcm(x,y)=2max(m0,n0)3max(m1,n1)5max(m2,n2)...

204. 计数质数

给定整数 n ,返回 所有小于非负整数 n 的质数的数量 。

示例 1:

输入:n = 10
输出:4
解释:小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

示例 2:

输入:n = 0
输出:0

示例 3:

输入:n = 1
输出:0

提示:

  • 0 < = n < = 5 ∗ 1 0 6 0 <= n <= 5 * 10^6 0<=n<=5106

思路:(埃式筛法)

埃式筛法

埃拉托斯特尼算法是希腊数学家埃拉托斯特尼(阿基米德的好友)发明的用来筛选素数的方法,为了方便我们一般简称为埃式筛法或者筛法。

  • 埃式筛法的思路非常简单,就是用已经筛选出来的素数过滤所有能够被它整除的数
  • 这些素数就像是筛子一样去过滤自然数,最后被筛剩下的数自然就是 不能被前面素数整除的数,根据素数的定义,这些剩下的数也是素数。

我们要筛选出n以内的所有素数:
1、我们知道2是最小的素数,我们先用2可以筛掉所有的偶数。
2、然后往后遍历到3,3是被2筛剩下的第一个数,也是素数,我们再用3去筛除所有能被3整除的数。
3、筛完之后我们继续往后遍历,第一个遇到的数是5,所以5也是素数,我们再重复以上的过程,直到遍历结束为止。
……
结束的时候,我们就获得了n以内的所有素数。

极致优化(线性筛)

  • 筛法的复杂度已经非常近似 O ( n ) O(n) O(n)了,因为即使在n很大的时候,经过两次ln的计算,也非常近似常数了,实际上在绝大多数使用场景当中,上面的算法已经足够应用了。
  • 但是仍然有大牛不知满足,继续对算法做出了优化,将其优化到了
    的复杂度。虽然从效率上来看并没有数量级的提升,但是应用到的思想非常巧妙,值得我们学习。

比较明显地可以看出来,对于一个合数而言,它可能会被多个素数筛去。比如12,它有23这两个素因数,那么它就会被置为两次;

这就带来了额外的开销,如果对于每一个合数我们只更新一次,那么是不是就能优化到 O ( n ) O(n) O(n)了呢?

  • 这里要用到上面素数分解的定理,就是每个合数分解质因数的结果是唯一的。既然是唯一的,那么一定可以找到最小的质因数,如果我们能够保证一个合数只会被它最小的质因数更新为True,那么整个优化就完成了。

那我们具体怎么做呢?其实也不难:
1、我们假设整数n的最小质因数是m
2、那么我们用小于m的素数i乘上n可以得到一个合数。我们将这个合数消除;
3、对于这个合数而言,i 一定是它最小的质因数。因为它等于i * nn最小的质因数是mi 又小于m,所以i是它最小的质因数。
……
我们用这样的方法来生成消除的合数,这样来保证每个合数只会被它最小的质因数消除。

代码:(Java)

public class CountPrimes {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int n = 10;
		System.out.println(countPrimes(n));
	}
	public static int countPrimes(int n) {
		if(n <= 1) {
			return 0;
		}
		int count = 0; //个数
		boolean[] notPrimes = new boolean[n + 1]; //数组存储是否为素数
		
		for(int i = 2; i < n; i++) {
			if(notPrimes[i]) {
				continue;
			}
			count++;
			//i是素数
			//从 i * i开始(如果 k < i ,那么 k*i 在之前就已经去除过了)
			for(long j = (long)i * i; j < n; j += i) {
				notPrimes[(int) j] = true;
			}
		}
		return count;
    }
}

极致优化(线性筛)

import java.util.ArrayList;
import java.util.List;

public class CountPrimes {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int n = 10;
		System.out.println(countPrimes(n));
	}
	public static int countPrimes(int n) {
		if(n <= 1) {
			return 0;
		}
		
		boolean[] notPrimes = new boolean[n + 1]; 
		List<Integer> primes = new ArrayList<Integer>();
		
		for(int i = 2; i < n; i++) {
			if(!notPrimes[i]) {//如果是素数则加入primes
				primes.add(i);
			}
			for(int j = 0; j < primes.size() && i * primes.get(j) < n; j++) {
				notPrimes[i * primes.get(j)] = true;
				if(i % primes.get(j) == 0) {// 到 合数i 的最小质数时,停止
					break;
				}
			}
		}
		return primes.size();
    }
}

运行结果:

在这里插入图片描述

复杂度分析:

埃式筛法

  • 时间复杂度 O ( n ∗ l n l n ( n ) ) O(n*lnln(n)) O(nlnln(n)),我们一共有了两层循环,最外面一层循环固定是遍历n次。而里面的这一层循环遍历的次数一直在变化,并且它的运算次数和素数的大小相关,看起来似乎不太方便计算。实际上是可以的,根据素数分布定理以及一系列复杂的运算.
  • 空间复杂度 O ( n ) O(n) O(n),需要开辟长度为n的数组,n为给定的整数

极致优化(线性筛)

  • 时间复杂度 O ( n ) O(n) O(n),赋值的次数减少了.
  • 空间复杂度 O ( n ) O(n) O(n).

注:仅供学习参考, 如有不足,欢迎指正!

题目来源:力扣。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/3434.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【三】一起算法---栈:STL stack、手写栈、单调栈

纸上得来终觉浅&#xff0c;绝知此事要躬行。大家好&#xff01;我是霜淮子&#xff0c;欢迎订阅我的专栏《算法系列》。 学习经典算法和经典代码&#xff0c;建立算法思维&#xff1b;大量编码让代码成为我们大脑的一部分。 ⭐️已更系列 1、基础数据结构 1.1、链表➡传送门 1…

使用Node.js+Koa 从零开始写个人博客系统——后端部分(一)

使用Node.jsKoa 从零开始写个人博客系统系列 提示&#xff1a;在此文章中你可以学习到的内容如下&#xff1a; 1 如何使用Koa快速搭建项目 2 对Koa的核心组件Koa-Route的简单使用 3 3层架构思想 4 nodejs的ORM框架——sequelize的使用 5 sequelize-auto的使用 6 简单的增删查改…

【蓝桥杯嵌入式】第十三届蓝桥杯嵌入式国赛客观题以及详细题解

题1 概念题。 USRAT&#xff1a;异步串口通信&#xff0c;常用于数据传输&#xff1b;SW-DP&#xff1a;SWD 的全称应该是 The Serial Wire Debug Port (SW-DP),也就是串行调试端口&#xff0c;是 >ARM 目前支持的两种调试端口之一&#xff1b;JTAG-DP&#xff1a;另一个调试…

git基本用法教程(fork软件+git命令)

git基本用法教程1. git commit2. git branch3. git checkout4. git merge5. git rebase6. 在提交树中移动7. 撤销变更8. 整理提交记录9. 提交的技巧10. git clone11. git push12. git pull13. git fetch14. git flow15. git stash16. fork的使用当然除了环境和demo的运行和改写…

chartgpt 告诉我的,loss 函数的各种知识

一、libtorch中常见的损失函数及其使用场景的总结1. CrossEntropyLoss:CrossEntropyLoss&#xff08;交叉熵损失&#xff09;主要用于分类任务。它适用于多分类问题&#xff0c;其中每个样本只属于一个类别&#xff08;互斥&#xff09;。该损失函数将预测概率与真实标签的one-…

应届生投腾讯,被面试官问了8个和 ThreadLocal 相关的问题。

问&#xff1a;谈一谈ThreadLocal的结构。 ThreadLocal内部维护了一个ThreadLocalMap静态内部类&#xff0c;ThreadLocalMap中又维护了一个Entry静态内部类&#xff0c;和Entry数组。 Entry类继承弱引用类WeakReference&#xff0c;Entry类有一个有参构造函数&#xff0c;参数…

【数据结构】用队列实现栈

&#x1f4af;&#x1f4af;&#x1f4af; 本篇总结利用队列如何实现栈的相关操作&#xff0c;不难观察&#xff0c;栈和队列是可以相互转化的&#xff0c;需要好好总结它们的特性&#xff0c;构造出一个恰当的结构来实现即可&#xff0c;所以本篇难点不在代码思维&#xff0c;…

大数据应用——Hadoop运行模式(伪分布式运行)

4.2 伪分布式运行模式4.2.1 启动HDFS并运行MapReduce程序1. 分析 &#xff08;1&#xff09;配置集群&#xff08;2&#xff09;启动、测试集群增、删、查没有改&#xff08;多台机子麻烦&#xff09;&#xff08;3&#xff09;执行WordCount案例2. 执行步骤&#xff08;1&…

前端vue实现导出pdf文件报告组件

大屏项目有一个需求&#xff0c;需要对展示的内容进行文件导出&#xff0c;但是目前后台没有相关的逻辑&#xff0c;所以只能前端硬上&#xff0c;在参考了其他许多的逻辑之后&#xff0c;目前我自己这边做了一套比较笨的组件&#xff0c;通过拼接标签这种方法来实现对你想需要…

队列-我的基础算法刷题之路(六)

本篇博客旨在整理记录自已对队列的一些总结&#xff0c;以及刷题的解题思路&#xff0c;同时希望可给小伙伴一些帮助。本人也是算法小白&#xff0c;水平有限&#xff0c;如果文章中有什么错误之处&#xff0c;希望小伙伴们可以在评论区指出来&#xff0c;共勉 &#x1f4aa;。…

seaborn从入门到精通03-绘图功能实现02-分类绘图Categorical plots

seaborn从入门到精通03-绘图功能实现02-分类绘图Categorical plots总结参考关系-分布-分类分类绘图-Visualizing categorical data图形级接口catplot--figure-level interface导入库与查看tips和diamonds 数据分类散点图参考分布散点图stripplot分布密度散点图-swarmplot&#…

进程与线程

文章目录进程与线程进程什么是进程进程的组成程序段数据段程序控制块例子线程什么是线程线程的组成线程描述信息程序计数器栈内存例子进程与线程的区别进程与线程 进程 什么是进程 ​ 什么是进程呢&#xff1f;简单来说&#xff0c;进程是程序的一次启动执行。什么是 程序呢…

【C#进阶】C# 集合类

序号系列文章16【C#进阶】C# 索引器17【C#进阶】C# 委托18【C#进阶】C# 事件文章目录前言1、集合类是什么2、动态数组&#xff08;ArrayList&#xff09;3、压缩数组&#xff08;BitArray&#xff09;4、哈希表&#xff08;Hashtable&#xff09;5、队列&#xff08;Queue&…

【数据结构】链表OJ题

目录面试题 02.04 分割链表剑指 Offer II 027 回文链表160 相交链表141 环形链表142 环形链表 II138 复制带随机指针的链表面试题 02.04 分割链表 定义lesshead和greaterhead链接小于和大于等于k的值分别设置哨兵位和尾节点指针最后将两表去除哨兵位再链接 struct ListNode* p…

内存泄漏和内存溢出的区别

参考答案 内存溢出(out of memory)&#xff1a;指程序在申请内存时&#xff0c;没有足够的内存空间供其使用&#xff0c;出现 out of memory。内存泄露(memory leak)&#xff1a;指程序在申请内存后&#xff0c;无法释放已申请的内存空间&#xff0c;内存泄露堆积会导致内存被…

论文解读:PP-LiteSeg: A Superior Real-Time Semantic Segmentation Model

发表时间&#xff1a;2022 论文地址&#xff1a;https://arxiv.org/abs/2204.02681 项目地址&#xff1a;https://github.com/PaddlePaddle/PaddleSeg PP-LiteSeg&#xff0c;一个新的轻量级实时语义分割任务模型&#xff0c;在分割精度和推理速度之间实现了一种最先进的权衡…

JVM垃圾回收机制

文章目录JVM垃圾回收机制如何确定该对象是垃圾引用计数可达性分析如何释放对象常用策略JVM垃圾回收机制 以对象为单位来进行回收 如何确定该对象是垃圾 Java 中使用 可达性分析方法 Python 中时使用 引用计数方法 引用计数 使用额外的计数器&#xff0c;来记录某个对象有多少个…

【致敬未来的攻城狮计划】连续打卡第4天+物联网操作系统概述

开启攻城狮的成长之旅&#xff01;这是我参与的由 CSDN博客专家 架构师李肯&#xff08;http://yyds.recan-li.cn&#xff09;和 瑞萨MCU &#xff08;https://www.renesas.cn/cn/zh&#xff09; 联合发起的「 致敬未来的攻城狮计划 」的第 4 天&#xff0c;点击查看活动计划详…

【Vue3】用Element Plus实现列表界面

&#x1f3c6;今日学习目标&#xff1a;用Element Plus实现列表界面 &#x1f603;创作者&#xff1a;颜颜yan_ ✨个人格言&#xff1a;生如芥子&#xff0c;心藏须弥 ⏰本期期数&#xff1a;第四期 &#x1f389;专栏系列&#xff1a;Vue3 文章目录前言效果图目录简介修改vite…

基于springboot框架实现心理健康心灵治愈交流平台【源码+论文】展示

基于springboot框架实现心灵心理健康 【源码论文】开发语言&#xff1a;Java 框架&#xff1a;springboot JDK版本&#xff1a;JDK1.8 服务器&#xff1a;tomcat7 数据库&#xff1a;mysql 5.7 数据库工具&#xff1a;Navicat11 开发软件&#xff1a;eclipse/myeclipse/idea Ma…