【编程基础C++】素数判定、最小公倍数与最大公因数的实现方法

本文主要是介绍【编程基础C++】素数判定、最小公倍数与最大公因数的实现方法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 素数
    • 法一
    • 法二
  • 最大公因数
    • 辗转相除法
    • 另一写法
  • 最小公倍数
    • 直接枚举法
    • 根据GCD算LCM

素数

素数 是指大于1的自然数,且只能被1和自身整除。例如,2、3、5和7都是素数。它们在数学中非常重要,因为任何大于1的自然数都可以唯一地表示为素数的乘积,这被称为素数分解。

法一

#include <iostream>
using namespace std;bool IsPrime(int n)
{if(n <= 1){cout << n << "不是素数" << endl; return false;}for (int i = 2; i < n; i++){if ((n % i) == 0){cout << n << "不是素数" << endl;return false;}}cout << n << "是素数" << endl;return true;
}

法二

#include <iostream>
#include <algorithm>
using namespace std;bool IsPrime(int n)
{if(n <= 1){return false;}for (int i = 2; i <sqrt(n); i++){if ((n % i) == 0){return false;}}return true;
}

最大公因数

最大公因数(GCD) 是指两个或多个整数的最大正整数因子,它们共同的因子中最大的一个。比如,24和36的最大公因数是12,因为12是24和36的所有公因数中最大的。常用的计算方法包括辗转相除法。

辗转相除法

// 辗转相除法求最大公因数
int gcd(int a, int b) {while (b != 0) {int temp = b;b = a % b;a = temp;}return a;
}

另一写法

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

最小公倍数

最小公倍数(LCM) 是指两个或多个整数的最小正整数倍数。换句话说,它是能被这些整数整除的最小数。例如,对于数字4和6,它们的最小公倍数是12,因为12是4和6的所有倍数中最小的一个。

计算最小公倍数的一种常用方法是利用最大公因数(GCD)。公式如下:

在这里插入图片描述

其中,a 和 b 是要计算最小公倍数的两个数,GCD(a, b) 是它们的最大公因数。这个公式利用了最大公因数和最小公倍数之间的关系,使得计算过程更加高效。

直接枚举法

int lcm(int a, int b) {int multiple = std::max(a, b);while (true) {if (multiple % a == 0 && multiple % b == 0)return multiple;multiple++;}
}

根据GCD算LCM

// 计算最小公倍数
int lcm(int a, int b) {return (a * b) / gcd(a, b);
}

这篇关于【编程基础C++】素数判定、最小公倍数与最大公因数的实现方法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1136872

相关文章

postgresql使用UUID函数的方法

《postgresql使用UUID函数的方法》本文给大家介绍postgresql使用UUID函数的方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录PostgreSQL有两种生成uuid的方法。可以先通过sql查看是否已安装扩展函数,和可以安装的扩展函数

Python实现终端清屏的几种方式详解

《Python实现终端清屏的几种方式详解》在使用Python进行终端交互式编程时,我们经常需要清空当前终端屏幕的内容,本文为大家整理了几种常见的实现方法,有需要的小伙伴可以参考下... 目录方法一:使用 `os` 模块调用系统命令方法二:使用 `subprocess` 模块执行命令方法三:打印多个换行符模拟

SpringBoot+EasyPOI轻松实现Excel和Word导出PDF

《SpringBoot+EasyPOI轻松实现Excel和Word导出PDF》在企业级开发中,将Excel和Word文档导出为PDF是常见需求,本文将结合​​EasyPOI和​​Aspose系列工具实... 目录一、环境准备与依赖配置1.1 方案选型1.2 依赖配置(商业库方案)二、Excel 导出 PDF

Python实现MQTT通信的示例代码

《Python实现MQTT通信的示例代码》本文主要介绍了Python实现MQTT通信的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录1. 安装paho-mqtt库‌2. 搭建MQTT代理服务器(Broker)‌‌3. pytho

Java中Arrays类和Collections类常用方法示例详解

《Java中Arrays类和Collections类常用方法示例详解》本文总结了Java中Arrays和Collections类的常用方法,涵盖数组填充、排序、搜索、复制、列表转换等操作,帮助开发者高... 目录Arrays.fill()相关用法Arrays.toString()Arrays.sort()A

使用zip4j实现Java中的ZIP文件加密压缩的操作方法

《使用zip4j实现Java中的ZIP文件加密压缩的操作方法》本文介绍如何通过Maven集成zip4j1.3.2库创建带密码保护的ZIP文件,涵盖依赖配置、代码示例及加密原理,确保数据安全性,感兴趣的... 目录1. zip4j库介绍和版本1.1 zip4j库概述1.2 zip4j的版本演变1.3 zip4

Nginx安全防护的多种方法

《Nginx安全防护的多种方法》在生产环境中,需要隐藏Nginx的版本号,以避免泄漏Nginx的版本,使攻击者不能针对特定版本进行攻击,下面就来介绍一下Nginx安全防护的方法,感兴趣的可以了解一下... 目录核心安全配置1.编译安装 Nginx2.隐藏版本号3.限制危险请求方法4.请求限制(CC攻击防御)

python生成随机唯一id的几种实现方法

《python生成随机唯一id的几种实现方法》在Python中生成随机唯一ID有多种方法,根据不同的需求场景可以选择最适合的方案,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习... 目录方法 1:使用 UUID 模块(推荐)方法 2:使用 Secrets 模块(安全敏感场景)方法

MyBatis-Plus通用中等、大量数据分批查询和处理方法

《MyBatis-Plus通用中等、大量数据分批查询和处理方法》文章介绍MyBatis-Plus分页查询处理,通过函数式接口与Lambda表达式实现通用逻辑,方法抽象但功能强大,建议扩展分批处理及流式... 目录函数式接口获取分页数据接口数据处理接口通用逻辑工具类使用方法简单查询自定义查询方法总结函数式接口

C++中全局变量和局部变量的区别

《C++中全局变量和局部变量的区别》本文主要介绍了C++中全局变量和局部变量的区别,全局变量和局部变量在作用域和生命周期上有显著的区别,下面就来介绍一下,感兴趣的可以了解一下... 目录一、全局变量定义生命周期存储位置代码示例输出二、局部变量定义生命周期存储位置代码示例输出三、全局变量和局部变量的区别作用域