基础数论一:判定质数和求约数相关

1.试除法求质数

    质数就是大于1的整数中除了1和自身没有其他因数的数

1.1暴力求解

     暴力求解的思路就是从2遍历到自身判断是否有被整除的数,时间复杂度为O(n)的

bool is_prime(int x)
{
    if(x<2)return false;
    for(int i=2;i<x;i++)
    {
      if(x%i==0)
      {
         return false;
      }
    }
  return true;
}

1.2调用sqrt库函数

     因数是成对出现的,如果d是x的因数,则x/d也是x的因数,又因为d<=x/d,则有d^2<=x,所以我们只需要遍历到根号x即可,如果在此之前没有因数,则往后也不会有,因为因数是成对出现的

bool is_prime(int x)
{
    if(x<2)return false;
    for(int i=2;i<sqrt(x);i++)
    {
      if(x%i==0)
      {
         return false;
      }
    }
  return true;
}

     我们也可以不调用库函数,而转化为i*i<=x的形式,这和开根号的思路是一样的,但是有一个问题,就是在x很大时,i*i会很大,造成溢出,这是很容易出现的问题,而调用库函数往往效率也是比较低的,所以我们必须要优化!

1.3试除法

     刚才我们提到如果d是x的因数,x/d也是x的因数,当其中一个存在时,另一个也必然存在;如果其中一个不存在,那么另一个也不存在,所以判断前面那一个就行了。

bool is_prime(int x)
{
    if(x<2)return false;
    for(int i=2;i<=x/i;i++)
    {
      if(x%i==0)
      {
         return false;
      }
    }
  return true;
}

      这样就将时间复杂度从O(n)降到了O(sqrt(n))。

2.试除法求约数

    前面我们知道如果d是x的因数,则x/i也是x的因数,所以我们只需要遍历前一部分即可,当i是x的因数时,我们要判断i是否等于x/i,如果不等于,就加入x/i,否则不加。

vector<int> get_divisors(int x)
{
	vector<int>res;
	for (int i = 1; i <= x / i; i++)
	{
		if (x % i == 0)
		{
			res.push_back(i);
			if (x != x / i)res.push_back(x / i);
		}
	}
	sort(res.begin(), res.end());
	return res;
}

 完整实现

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> get_divisors(int x)
{
	vector<int>res;
	for (int i = 1; i <= x / i; i++)
	{
		if (x % i == 0)
		{
			res.push_back(i);
			if (x != x / i)res.push_back(x / i);
		}
	}
	sort(res.begin(), res.end());
	return res;
}
int main()
{
	int x;
	cout << "请输入一个整数:" << endl;
	cin >> x;
	vector<int>res = get_divisors(x);
	cout << "该整数的所有约数为:" ;
	for (auto num : res)
	{
		cout << num << " ";
	}
	return 0;
}

    

 3.欧几里得算法

     欧几里得算法又叫辗转相除法,用于计算两个非负整数a和b的最大公约数。

     两个整数的最大公约数是能够同时整除它们的最大正整数。欧几里得算法的原理是:两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。怎么来证明呢?方法如下:

设a、b且a>b,则有a=kb+r(k,r>0)
设a,b最大公约数为v,则有a=xv,b=yv(x,y>0)
                  所以r=a-kb=xv-kyv=(x-ky)v,得到r整除v
设b,r最大公约数为v,则有b=mv,r=nv(m,n>0)
                  所以a=kb+r=kmv+nv=(km+n)v,得到a整除v
所以(a,b)的最大公约数=(b,r)的最大公约数=(b,a%b)的最大公约数

3.1.代码实现

int gcd(int a,int b)
{
   return b?gcd(b,a%b):a;
}

3.2.演示

#include<stdio.h>
int gcd(int a, int b)
{
	return b ? gcd(b, a % b) : a;
}
int main()
{
	int a, b;
	printf("请输入两个整数:");
	scanf_s("%d %d", &a, &b);
	printf("a和b的最大公约数为:%d", gcd(a, b));
	return 0;
}

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

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

相关文章

第十七章 多线程基础

一、线程相关概念 1. 程序 程序&#xff1a;是为完成特定任务、用某种语言编写的一组指令的集合。 简单说就是代码。 2. 进程 &#xff08;1&#xff09;进程是指运行中的程序&#xff0c;比如我们使用QQ&#xff0c;就启动了一个进程&#xff0c;操作系统会为该进程分配内存空…

离职的赔偿算法n 、n+1、2n你还不懂嘛?

亲爱的小伙伴们&#xff0c;由于微信公众号改版&#xff0c;打乱了发布时间&#xff0c;为了保证大家可以及时收到文章的推送&#xff0c;可以点击上方蓝字关注测试工程师成长之路&#xff0c;并设为星标就可以第一时间收到推送哦&#xff01; 哪些情况需要支付经济补偿? 劳动…

看图了解ODF光纤配线架,详细熔接过程学习

弱电工程&#xff0c;远距离传输离不开光纤&#xff0c;只有光纤才能让网络传输的更远&#xff0c;今天了解光纤的配套产品&#xff0c;光纤配线架&#xff08;Optical Distribution Frame&#xff09;用于光纤通信系统中局端主干光缆的成端和分配&#xff0c;可方便地实现光纤…

【Python】requests库在CTFWeb题中的应用

目录 ①Bugku-GET ②Bugku-POST ③实验吧-天下武功唯快不破 ④Bugku-速度要快 ⑤Bugku-秋名山车神 ⑥Bugku-cookies ①Bugku-GET import requestsresprequests.get(urlhttp://114.67.175.224:12922/,params{what:flag}) print(resp.text)//或者 //resprequests.get(urlht…

使用Visual Studio调试VisionPro脚本

使用Visual Studio调试VisionPro脚本 方法一 &#xff1a; 修改项目文件 csproj步骤&#xff1a; 方法二 &#xff1a; Visual Studio附加功能步骤&#xff1a; 方法一 &#xff1a; 修改项目文件 csproj 步骤&#xff1a; 开启VisionPro脚本调试功能 创建一个VisionPro程序…

VBA技术资料MF99:在代码中使用VLookUp函数

我给VBA的定义&#xff1a;VBA是个人小型自动化处理的有效工具。利用好了&#xff0c;可以大大提高自己的工作效率&#xff0c;而且可以提高数据的准确度。我的教程一共九套&#xff0c;分为初级、中级、高级三大部分。是对VBA的系统讲解&#xff0c;从简单的入门&#xff0c;到…

华为数通方向HCIP-DataCom H12-831题库(多选题:221-240)

第221题 在割接项目的项目调研阶段需要对现网硬件环境进行观察,主要包括以下哪些内容? A、设备的位置 B、ODF位置 C、接口标识 D、光纤接口对应关系 答案:ABCD 解析: 在项目割接前提的项目调研阶段,需要记录下尽可能详细的信息。 第222题 以下哪些项能被正则表达式10*成…

每日一题——LeetCode206.反转链表

个人主页&#xff1a;白日依山璟 专栏&#xff1a;Java|数据结构与算法|每日一题 文章目录 1. 题目描述示例1示例2示例3提示 2. 思路3.代码 1. 题目描述 给你单链表的头节点 head &#xff0c;请你反转链表&#xff0c;并返回反转后的链表。 示例1 输入&#xff1a;head [1…

<JavaEE> TCP 的通信机制 -- 确认应答 和 超时重传

目录 TCP的通信机制的核心特性 一、确认应答 1&#xff09;什么是确认应答&#xff1f; 2&#xff09;如何“确认”&#xff1f; 3&#xff09;如何“应答”&#xff1f; 二、超时重传 1&#xff09;丢包的概念 2&#xff09;什么是超时重传&#xff1f; 3&#xff09…

算法leetcode|94. 二叉树的中序遍历(多语言实现)

文章目录 94. 二叉树的中序遍历&#xff1a;样例 1&#xff1a;样例 2&#xff1a;样例 3&#xff1a;提示&#xff1a; 分析&#xff1a;题解&#xff1a;rust&#xff1a;go&#xff1a;c&#xff1a;python&#xff1a;java&#xff1a; 94. 二叉树的中序遍历&#xff1a; …

什么样的产品适合建设私域流量池?

私域流量是什么&#xff1f;公域流量和私域流量是相对概念&#xff0c;触达和运营更加自由的流量称为私域流 量。私域流量的形态&#xff0c;我们称为私域流量池。私域流量池本质是便捷和低成本的运营方式&#xff0c; 运营用户&#xff0c;追求更便宜的流量来源、更高的售卖转…

什么是动态IP?静态IP和动态IP有什么区别?

动态IP(Dynamic IP)和静态IP(Static IP)它是指在计算机网络中分配给设备的两种不同类型的IP地址。 动态IP是指每次设备连接到网络时&#xff0c;网络服务提供商(ISP)IP地址的动态分配。当设备重新连接到网络时&#xff0c;它可能会被分配到不同的IP地址。动态IP适用于传统的家…

通过IntersectionObserver实现图片下拉加载(瀑布流布局)

效果展示&#xff1a; 瀑布流上拉加载 目录结构 html: <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8" /><meta http-equiv"X-UA-Compatible" content"IEedge" /><meta name"vie…

力扣刷题记录(18)LeetCode:474、518、377、322

目录 474. 一和零 518. 零钱兑换 II 377. 组合总和 Ⅳ 322. 零钱兑换 总结&#xff1a; 474. 一和零 这道题和前面的思路一样&#xff0c;就是需要将背包扩展到二维。 class Solution { public:int findMaxForm(vector<string>& strs, int m, int n) {vector&l…

KNN与KD树博客总结

目录 总结小结&#xff1a; 总结 原始篇&#xff1a;KNN算法及其优缺点算法思想改进篇&#xff1a;KD树&#xff08;KNN的plus版算法实现第一篇&#xff1a;平衡二叉树的构建&#xff08;递归算法实现第二篇&#xff1a;KD树的构建&#xff08;递归算法实现第三篇&#xff1a;…

开源持续测试平台Linux MeterSphere本地部署与远程访问

文章目录 前言1. 安装MeterSphere2. 本地访问MeterSphere3. 安装 cpolar内网穿透软件4. 配置MeterSphere公网访问地址5. 公网远程访问MeterSphere6. 固定MeterSphere公网地址 前言 MeterSphere 是一站式开源持续测试平台, 涵盖测试跟踪、接口测试、UI 测试和性能测试等功能&am…

windows安全配置实验手册

访问控制策略&#xff08;L1940520022J&#xff09; 预备知识 Windows 7中&#xff0c;不仅有面向软件的限制方法&#xff0c;还增加了一种名为AppLocker的访问控制策略&#xff08;仅适用于企业版和旗舰版&#xff09;。 实验环境 操作系统类型&#xff1a;windows 7。 实…

【问题记录-ASIO】Audition多通道ASIO驱动提示“(不工作)“问题

一&#xff0c;问题现象 在使用Audition打开多通道工程&#xff0c;使用ASIO驱动&#xff0c;却发现设备提示“不工作”&#xff0c;如下图所示&#xff1a; 二&#xff0c;解决方法 2.1 声卡设备枚举确认 首先确认声卡设备枚举是否成功&#xff0c;如果没有枚举成功&…

【SpringCloud笔记】(10)消息总线之Bus

Bus 前言 戳我了解Config 学习Config中我们遇到了一个问题&#xff1a; 当我们修改了GitHub上配置文件内容&#xff0c;微服务需要配置动态刷新并且需要手动向客户端发送post请求刷新微服务之后才能获取到GitHub修改过后的内容 假如有多个微服务客户端3355/3366/3377…等等…

将本地镜像推送到阿里云

文章目录 创建仓库镜像登录 并上传下载上传的 创建仓库镜像 利用下面的脚本进行配置 登录 并上传 [roothadoop100 ~]# docker login --username13thm registry.cn-hangzhou.aliyuncs.com Password: [roothadoop100 ~]# docker tag ba78e6d6845c registry-vpc.cn-hangzhou.al…