双子数(枚举素数)

 

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;vector<long long> generate(long long n) {vector<bool> is(n + 1, true);// 标记是否为素数,初始值全为 truevector<long long> v;is[0] = is[1] = false;  // 0 和 1 不是素数for (long long i = 2; i <= n; i++) {if (is[i]) {v.push_back(i);  // 如果当前数是素数,存入结果数组for (long long j = i * i; j <= n; j += i) {is[j] = false;  // 将当前素数的倍数标记为非素数}}}return v;
}int main() {int a = 2333;long long b = 23333333333333;long long n = sqrt(b);vector<long long> v = generate(n); // 生成所有小于等于 sqrt(b) 的素数long long ans = 0;for (int i = 0; i < v.size(); i++) {long long p = v[i];long long p2 = p * p;   // p 的平方,提前计算以减少重复计算for (int j = i + 1; j < v.size(); j++) {long long q = v[j];long long q2 = q * q;if (p > b / q2) break; // 提前判断是否溢出,避免计算 p^2 * q^2 导致超出 long long 范围long long x = p2 * q2;if (x >= a && x <= b) {// 检查是否在区间范围内,满足条件则计入答案ans++;}}}cout << ans;return 0;
}

long long j = i * i; j <= n; j += i

目的是在使用埃拉托色尼筛法时将素数 i 的所有倍数标记为非素数。

在筛法中,素数 i 的所有倍数可以从 i^2 开始筛除。因为对于所有小于 i^2 的倍数 i×k(其中 k<i),这些倍数在之前的迭代中已经被标记为非素数。

j += i:这步是使得从 i^2 开始的每个 i 的倍数都被标记为非素数。每次加上 i,这样可以确保我们遍历到的所有倍数是 i 的倍数。

提前计算 q² > b / p² 来避免乘法溢出。也就是b < q² * p² 的情况break

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Springboot集成ElasticSearch实现minio文件内容全文检索

一、docker安装Elasticsearch &#xff08;1&#xff09;springboot和Elasticsearch的版本对应关系如下&#xff0c;请看版本对应&#xff1a; 注意安装对应版本&#xff0c;否则可能会出现一些未知的错误。 &#xff08;2&#xff09;拉取镜像 docker pull elasticsearch:7…

思源笔记 Creating group siyuan (1000) permission denied (are you root?)

错误提示 siyuan_jx85-1 | Creating group siyuan (1000) siyuan_jx85-1 | addgroup: permission denied (are you root?) siyuan_jx85-1 | Creating group siyuan (1000) siyuan_jx85-1 | addgroup: permission denied (are you root?) siyuan_jx85-1 | Creating group siy…

基于Matlab的碎纸片的自动拼接复原技术

碎纸片的自动拼接复原技术 摘要&#xff1a;破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。目前发现对碎纸片的拼接大部分由人工完成&#xff0c;准确率较高&#xff0c;但耗费大量人力财力及时间&#xff0c;效率很低。随着计算机技术的…

SpringBoot(5)-SpringSecurity

目录 一、是什么 二、实战测试 2.1 认识 2.2 认证和授权 2.3 权限控制和注销 2.4 记住我 一、是什么 Spring Security是一个框架&#xff0c;侧重于为java应用程序提供身份验证和授权。 Web应用的安全性主要分为两个部分&#xff1a; 认证&#xff08;Authentication&…

【eNSP】企业网络架构实验——vlan间的路由通信(三)

VLAN间的路由是指不同VLAN之间的通信&#xff0c;通常VLAN是用来分割网络流量和提高网络安全性的。 一、VLAN 1. 什么是VLAN&#xff1f; VLAN&#xff0c;全称是虚拟局域网&#xff08;Virtual Local Area Network&#xff09;&#xff0c;是一种将物理局域网&#xff08;LA…

DAY65||Bellman_ford 队列优化算法(又名SPFA)|bellman_ford之判断负权回路|bellman_ford之单源有限最短路

Bellman_ford 队列优化算法&#xff08;又名SPFA&#xff09; 94. 城市间货物运输 I 思路 大家可以发现 Bellman_ford 算法每次松弛 都是对所有边进行松弛。 但真正有效的松弛&#xff0c;是基于已经计算过的节点在做的松弛。 给大家举一个例子&#xff1a; 本图中&#xff…

FRP 实现内网穿透

如何通过 FRP 实现内网穿透&#xff1a;群晖 NAS 的 Gitea 和 GitLab 访问配置指南 在自建服务的过程中&#xff0c;经常会遇到内网访问受限的问题。本文将介绍如何利用 FRP&#xff08;Fast Reverse Proxy&#xff09;来实现内网穿透&#xff0c;以便在外网访问群晖 NAS 上的…

【优选算法 — 滑动窗口】水果成篮 找到字符串中所有字母异位词

水果成篮 水果成篮 题目描述 因为只有两个篮子&#xff0c;每个篮子装的水果种类相同&#xff0c;如果从 0 开始摘&#xff0c;则只能摘 0 和 1 两个种类 &#xff1b; 因为当我们在两个果篮都装有水果的情况下&#xff0c;如果再走到下一颗果树&#xff0c;果树的水果种类…

1、使用vscode+eide+stm32cubeMx开发stm32

步骤1&#xff1a;在vscode中安装如下的插件 步骤2&#xff1a;点击Embedded IDE&#xff0c;点击“新建项目”-----空项目-----Cortex-M项目。 步骤3&#xff1a;输入项目名&#xff0c;回车后会要制定保存路径&#xff0c;此时就是一个已项目名命名的文件夹。 步骤4&#xff…

【数据库系列】 Spring Boot 集成 Neo4j 的详细介绍

Spring Boot 提供了对 Neo4j 的良好支持&#xff0c;使得开发者可以更方便地使用图数据库。通过使用 Spring Data Neo4j&#xff0c;开发者可以轻松地进行数据访问、操作以及管理。本文将详细介绍如何在 Spring Boot 应用中集成 Neo4j&#xff0c;包括基本配置、实体定义、数据…

高亚科技签约美妥维志化工,提升业务协同与项目运营效率

近日&#xff0c;中国企业管理软件资深服务商高亚科技与韶关美妥维志化工有限公司&#xff08;以下简称“美妥维志”&#xff09;正式签约。基于高亚科技的8Manage PM项目管理软件&#xff0c;美妥维志将实现项目进度、人员审批及问题的统一管理&#xff0c;提升部门间协同效率…

Python安装(ubuntu)

一&#xff1a;安装指定版本的python python3 --version直接返回ubuntu自带的3.8.10的版本 radarswradarsw-Precision-5560:~$ python3 --version Python 3.8.10通过指令直接安装&#xff0c;会报错如下; radarswradarsw-Precision-5560:~$ sudo apt install python3.11 正在…

大模型基础BERT——Transformers的双向编码器表示

大模型基础BERT——Transformers的双向编码器表示 整体概况 BERT&#xff1a;用于语言理解的深度双向Transform的预训练 论文题目&#xff1a;BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding Bidirectional Encoder Representations from…

云计算复习文档

云计算复习文档 一 云计算概述 名词&#xff1a; 云计算 1.0 &#xff1a; 面向数据中心管理员的IT基础设施资源虚拟化阶段 通过计算虚拟化技术将企业IT应用与底层的基础设施彻底分离、解耦 将多个企业IT应用实例及运行环境复用在相同的物理服务器上&#xff0c;并通过虚…

探索大规模语言模型(LLM)在心理健康护理领域中的应用与潜力

概述 心理健康是公共卫生最重要的领域之一。根据美国国家精神卫生研究所&#xff08;NIMH&#xff09;的数据&#xff0c;到 2021 年&#xff0c;22.8% 的美国成年人将患上某种形式的精神疾病。在全球范围内&#xff0c;精神疾病占非致命性疾病负担的 30%&#xff0c;并被世界…

Tensorflow基本概念

简介&#xff1a;本文从Graph讲到Session&#xff0c;同时讲解了tf.constant创建tensor的用法和variable需要初始化的知识点&#xff0c;可以给你打好一个学习Tensorflow的基础。本文都是基于TensorFlow1.14.0的版本下运行。 本专栏将会系统的讲解TensorFlow在1.14.0版本下的各…

Ubuntu+ROS 机械臂拾取和放置

官方链接&#xff1a;https://github.com/skumra/baxter-pnp 1.下载并安装 SDK 依赖项 sudo apt-get install python-wstool python-rosdep 2.创建新的 catkin 工作区 mkdir -p ~/ros_ws/src cd ~/ros_ws/src 3.使用 wstool 下载 rosinstall 文件并将其复制到 Catkin 工作区…

w~视觉~合集23

我自己的原文哦~ https://blog.51cto.com/whaosoft/12548542 #DragGAN 在 AIGC 的神奇世界里&#xff0c;我们可以在图像上通过「拖曳」的方式&#xff0c;改变并合成自己想要的图像。比如让一头狮子转头并张嘴&#xff1a; 实现这一效果的研究出自华人一作领衔的「Drag You…

从电动汽车到车载充电器:LM317LBDR2G 线性稳压器在汽车中的多场景应用

附上LM317系列选型&#xff1a; LM317BD2TG-TO-263 LM317BTG-TO-220 LM317BD2TR4G-TO-263 LM317D2TG-TO-263 LM317D2TR4G-TO-263 LM317TG-TO-220 LM317LBDR2G-SOP-8 LM317LDR2G-SOP-8 LM317MABDTG-TO-252 LM317MABDTRKG-TO-252 LM317MA…

【已解决】git push一直提示输入用户名及密码、fatal: Could not read from remote repository的问题

问题描述&#xff1a; 在实操中&#xff0c;git push代码到github上一直提示输入用户名及密码&#xff0c;并且跳出的输入框输入用户名和密码后&#xff0c;报错找不到远程仓库 实际解决中&#xff0c;发现我环境有两个问题解决&#xff1a; git push一直提示输入用户名及密码…