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

第 100002(十万零二)个素数是多少?

题目描述

素数就是不能再进行等分的整数。比如7,11。而 9 不是素数,因为它可以平分为 3 等份。一般认为最小的素数是2,接着是 3,5,...
请问,第 100002(十万零二)个素数是多少?
请注意:“2” 是第一素数,“3” 是第二个素数,依此类推。
运行限制
最大运行时间:1s
最大运行内存: 128M

题目分析

对于这道题来说,难点在于运行时间只要1秒钟的问题

这个问题核心解决在于对素数的判定能不能够更快一点

先来看第一种,也是最慢的一种

第二种  稍微快一点

 

他确实也是快了一点点,但是可以帮我们解决问题吗?

确实能解决问题,但是运行的非常慢,时间复杂度是O(n)

 第三种,采用sqrt开根号的方式来继续这半找素数

这个方法比上面排查的数据更少

这个时间复杂度应该就是O(sqrt(n))

相对于上面的来说还是要快一点

第四种, 直接卡到x/i这个位置

我们还可以列举出更大的质数来进行测试

 每一个数都会除一下,基本上也是除到sqrt(x)这样一个位置

上面这道题基本上来说,就解决了。

知识拓展

讲一个查找20以内的所有素数,假定是查找到20,但是这个数据这个可能更大,这里我们用一种埃氏筛选法

来说一下原理

 这里贴一下测试代码

#include <stdio.h>
#include <stdlib.h>typedef long long ll;
//定义数组的大小
const int N = 10000000;//一千万个数据int visit[N];//记录合数
int cnt=0;//与prime关联的一个游标
int prime[N];//记录质数//找出到<= N这样一个素数的一个查找
void find_prime(int n)
{//外层循环,循环整体for(int i = 2;i <= n;i++) {//如果等于0的情况,就是一个质数if(!visit[i]) {prime[cnt++] = i;//它的倍数一定是一个合数,然后按步长增长for(ll j = i*i;j<=n;j+=i) {//全是合数visit[j] = 1;//相应的i就是1 }}}
}int main()
{find_prime(20);for(int i = 0;i < cnt;i++) {printf("%d ",prime[i]); }return 0;
}

下面在来说另外一种素数筛选方法

欧拉筛选也叫线性筛选法

用两句话来说明一下线性筛选法

第一:每一个合数都是被它的一个最小因子筛选掉的

第二:如果当前被筛选的是一个质数,那么质数*质数是可以筛选掉一部分合数,其实也是通过最小因子算出来的

第三:用已知的素数去筛选合数,避免重复筛选,避免重复筛选这个过程,就是一个位置,如果一旦被标记为合数之后,就不要重复标记为合数

一张图来说明一下线性筛选法

demo2.cpp

#include <stdio.h>
#include <stdlib.h>
#include <vector>using namespace std;vector<int> get_primes(int n) 
{vector<int> primes;vector<bool> is_prime(n+1,true);//默认为true的情况下其实是为这质数的//下面开始循环for(int i = 2;i <= n;i++) {if(is_prime[i]) {primes.push_back(i);}for(int j = 0;j < primes.size() && i * primes[j] <= n;j++) {//只要有因子这个数标记为falseis_prime[i * primes[j]] = false;//避免重复标记if(i % primes[j] == 0) {break;}}}return primes;//返回一个vector数组
}int main()
{vector<int> res = get_primes(20);//采用for循环的方式进行打印vector<int>::iterator it_begin = res.begin();vector<int>::iterator it_end = res.end();//采用for循环的方式for(it_begin;it_begin != it_end;it_begin++) {printf("%d ",*it_begin);}printf("\n-------------------\n");//这里说过prime可以看成一个数组for(int i = 0;i < res.size();i++) {printf("%d ",res[i]);//本身就可以当成数组对待}return 0;
}

相关文章:

第 100002(十万零二)个素数是多少?

题目描述 素数就是不能再进行等分的整数。比如7&#xff0c;11。而 9 不是素数&#xff0c;因为它可以平分为 3 等份。一般认为最小的素数是2&#xff0c;接着是 3&#xff0c;5&#xff0c;... 请问&#xff0c;第 100002(十万零二)个素数是多少&#xff1f; 请注意&#xff1…...

Lua迭代器

Lua迭代器 迭代器&#xff08;iterator&#xff09;是一种对象&#xff0c;它能够用来遍历标准模板库容器中的部分或全部元素&#xff0c;每个迭代器对象代表容器中的确定的地址。 在 Lua 中迭代器是一种支持指针类型的结构&#xff0c;它可以遍历集合的每一个元素。 泛型 f…...

同步与互斥之信号量

目录 1、信号量用于线程的互斥 验证 2、信号量用于线程的同步 验证 3、无名信号量用于进程间互斥 代码一 代码二 验证 4、有名信号量 用于进程间同步和互斥 验证 信号量广泛用于进程或线程间的同步和互斥&#xff0c;信号量本质上是一个非负的整数计数器&#xff0c;它…...

如何当个优秀的文档工程师?从 TC China 看技术文档工程师的自我修养

本文系 NebulaGraph Community Academic 技术文档工程师 Abby 的参会观感&#xff0c;讲述了她在中国技术传播大会分享的收获以及感悟。 据说&#xff0c;技术内容领域、传播领域的专家和决策者们会在中国技术传播大会「tcworld China 2022」大会上分享心得。作为一名技术文档工…...

如何学习k8s

学习Kubernetes可以遵循以下步骤&#xff1a; 了解Kubernetes的基本概念和架构。学习Kubernetes前&#xff0c;需要了解它的基本概念和组成部分&#xff0c;包括Pod、Service、ReplicaSet、Deployment、Namespace等等&#xff0c;同时也需要了解Kubernetes的整体架构和工作原理…...

【SSM】MyBatis(十.动态sql)

文章目录1.if2.where3.trim4.set5. choose when otherwise6.foreach6.1 批量删除6.2 批量增加7.sql1.if <select id"selectByMultiCondition" resultType"Car">select * from t_car where 1 1<if test"brand ! null and brand ! ">…...

最近很多人都在说 “前端已死”,讲讲我的看法

转自 : 掘金 作者 : Ethan_Zhou 现状 我记得去年脉脉的论调还都是 客户端已死&#xff0c;前后端还都是一片祥和&#xff0c;有秀工资的&#xff0c;有咨询客户端转前端的&#xff0c;怎么最近打开脉脉一看&#xff0c;风向变了&#xff1f; 随便刷几下&#xff0c;出来的信息…...

大家好,我是火旺技术

大家好&#xff0c;我是火旺技术 在Internet高速发展的今天&#xff0c;我们生活的各个领域都涉及到计算机的应用。这其中&#xff0c;家乡特色推荐的网络应用已经成为外国家乡推荐系统的一种很普遍的方式。不过&#xff0c;在国内&#xff0c;管理网站可能还处于起步阶段。 …...

【Java并发编程系列】全方位理解多线程几乎包含线程的所有操作哦

文章目录一、概述及目录二、实现多线程的方式2.1 继承Tread类&#xff0c;重写run方法。start方法2.2 实现Runnable方法&#xff0c;并实现run接口方法2.3 实现Callable接口重写call方法&#xff0c;Feature.get()获取返回值三、线程的执行流程3.1 执行流程3.2 start方法和 run…...

天宝S6测量机器人/天宝S6全站仪参数/教程/Trimble 天宝全站仪

TRIMBLE DR PLUS技术 Trimble DR Plus™距离测量技术实现更大范围的直接反射测量&#xff0c;不使用棱镜也能进行长距离测量。难以抵达或不安全的测 量目标&#xff0c;对Trimble S6来说不再是问题。Trimble DR Plus结合 了MagDrive™磁驱伺服技术&#xff0c;使测量的快捷和…...

c++基础知识汇总

目录 1、基础 1.2 注释 1.3 变量 1.4 常量 1.5 关键字 1.6 标识符命名规则 2 数据类型 2.1 整型 2.2 sizeof关键字 2.3 实型&#xff08;浮点型&#xff09; 2.4 字符型 2.5 转义字符 2.6 字符串型 2.7 布尔类型 bool 2.8 数据的输入 1、基础 1.2 注释 作用&a…...

重磅!基于GPT-4的全新智能编程助手 GitHub Copilot X 来了!

GitHub Copilot相信大家一定不陌生了&#xff0c;强大的智能代码补全功能一度让媒体直呼程序员要被替代。随着OpenAI推出全新的GPT-4&#xff0c;GitHub Copilot也在3月22日&#xff0c;推出了全新一代产品&#xff1a;GitHub Copilot X 。最新的GitHub Copilot X 不仅可以自动…...

第04章_运算符

第04章_运算符 &#x1f3e0;个人主页&#xff1a;shark-Gao &#x1f9d1;个人简介&#xff1a;大家好&#xff0c;我是shark-Gao&#xff0c;一个想要与大家共同进步的男人&#x1f609;&#x1f609; &#x1f389;目前状况&#xff1a;23届毕业生&#xff0c;目前在某公…...

Excel 文件比较工具:xlCompare 11.0 Crack

&#xff08;Excel 文件比较工具&#xff09;xlCompare 11.0 下载并安装最新版本的 xlCompare。下载是一个功能齐全的版本。 筛选匹配的行 筛选不同的行 仅显示两个 Excel 文件中存在的行&#xff0c;并排除新&#xff08;已删除&#xff09;行 隐藏在另一张工作表上具有相应行…...

802.1x认证原理

802.1x认证原理802.1X认证简介802.1X认证协议802.1X认证流程802.1X认证简介 定义&#xff1a;802.1x协议是一种基于端口的网络接入控制协议。基于端口的网络接入控制&#xff0c;是指在局域网接入设备的端口这一级验证用户身份&#xff0c;并且控制其访问权限。优点&#xff1…...

GPIO的八种模式分析

GPIO是general purpose input output,即通用输入输出端口&#xff0c;作用是负责外部器件的信息和控制外部器件工作。 GPIO有如下几个特点&#xff1a;1.不同型号的IO口数量不同&#xff1b;2&#xff0c;反转快速&#xff0c;每次翻转最快只需要两个时钟周期&#xff0c;以ST…...

携职教育:财会人常用必备,203个EXCEL快捷键汇总

会用快捷键的人早下班&#xff01; 作为财务人员如果你想要提高工作效率&#xff0c;不掌握一些Excel快捷键怎么行&#xff1f; 老板看见了&#xff0c;也会赞一声&#xff0c;“看&#xff0c;这就是专业。” 立马给你加薪&#xff08;划掉&#xff09;&#xff0c;工作效率这…...

【美赛】2023年ICM问题Z:奥运会的未来(思路、代码)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

CSS基础入门

CSS基础之语法 介绍 ​CSS&#xff08;层叠样式表&#xff09;是一门用来设计网页样式的语言&#xff0c;如网页的布局、字体、颜色搭配、视觉特效。作为WEB开发的基础技术之一&#xff0c;掌握CSS的语法和API对于我们构建丰富的网页是必须的。 基础语法 <style>div …...

可重入锁、读写锁、邮戳锁 详解

文章目录1、可重入锁&#xff08;递归锁&#xff09;2、读写锁2.1、读写分离2.2、从写锁到读锁&#xff0c;ReentrantReadWriteLock可以降级2.3、写锁和读锁是互斥的3、邮戳锁StampedLock3.1、是什么3.2、锁饥饿3.3、如何缓解锁饥饿问题呢3.3.1、使用“公平”策略3.3.2、Stampe…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

vue3+vite项目中使用.env文件环境变量方法

vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量&#xff0c;这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

20个超级好用的 CSS 动画库

分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码&#xff0c;而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库&#xff0c;可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画&#xff0c;可以包含在你的网页或应用项目中。 3.An…...