电影网站做多大会有风险,石家庄本地招聘信息网,施工企业的期间费用主要包括哪些,班级优化大师免费下载电脑版用质因数求解最大公约数#xff08;gcd#xff09;
思路分析#xff1a;
1、质因数#xff1a;(素因数或质因子)他指的是能整除给定正整数的质数。例如#xff1a;36可以分解为223*3#xff0c;其中2和3就是质因数。 2、质因数求解最大公约数#xff1a; 对每个数进行…用质因数求解最大公约数gcd
思路分析
1、质因数(素因数或质因子)他指的是能整除给定正整数的质数。例如36可以分解为223*3其中2和3就是质因数。 2、质因数求解最大公约数 对每个数进行质因数分解 找出所有数的共有质因数并取每个共有质因数的最低次幂 将这些最低次幂的质因数想乘得到的结果就是这些数的最大公约数。 gcdabpi的minaibi次方 * pj的minajbj次方
code
#include iostream
#include unordered_map
#include cmath// 辅助函数检查一个数是否是质数
bool is_prime(int n) {if (n 1) return false;if (n 3) return true;if (n % 2 0 || n % 3 0) return false;for (int i 5; i * i n; i 6) {if (n % i 0 || n % (i 2) 0)return false;}return true;
}// 辅助函数找到并返回一个数的所有质因数及其次数
std::unordered_mapint, int find_prime_factors(int n) {std::unordered_mapint, int factors;for (int i 2; i std::sqrt(n); i) {while (n % i 0) {factors[i];n / i;}}// 如果n仍然大于1那么它本身就是一个质数if (n 1) {factors[n] 1;}return factors;
}// 使用质因数分解来求解最大公约数
int gcd_by_prime_factors(int a, int b) {std::unordered_mapint, int factors_a find_prime_factors(a);std::unordered_mapint, int factors_b find_prime_factors(b);int gcd 1;for (const auto factor_a : factors_a) {int prime factor_a.first;int count_a factor_a.second;// 查找b的质因数中是否有prime并取其最小次数auto iter_b factors_b.find(prime);if (iter_b ! factors_b.end()) {int count_b iter_b-second;int min_count std::min(count_a, count_b);gcd * std::pow(prime, min_count);}}// 还需要考虑b中独有的质因数如果a中没有的话for (const auto factor_b : factors_b) {if (factors_a.find(factor_b.first) factors_a.end()) {int prime factor_b.first;int count_b factor_b.second;// 但由于我们只关心共有的质因数所以这里不增加gcd}}return gcd;
}int main() {int a 24;int b 36;std::cout GCD of a and b is: gcd_by_prime_factors(a, b) std::endl;return 0;
}用质因数求解最小公倍数lcm
思路分析
1、质因数(素因数或质因子)他指的是能整除给定正整数的质数。例如36可以分解为223*3其中2和3就是质因数。 2、质因数求解最小公倍数 对每个数进行质因数分解 找出所有数的共有质因数并取每个共有质因数的最高次幂 将这些最高次幂的质因数想乘得到的结果就是这些数的最小公倍数。 lcmabpi的maxaibi次方 * pj的maxajbj次方
code
#include iostream
#include unordered_map
#include cmath// 辅助函数找到并返回一个数的所有质因数及其次数
std::unordered_mapint, int find_prime_factors(int n) {std::unordered_mapint, int factors;for (int i 2; i std::sqrt(n); i) {while (n % i 0) {factors[i];n / i;}}// 如果n仍然大于1那么它本身就是一个质数if (n 1) {factors[n] 1;}return factors;
}// 使用质因数分解来求解最小公倍数
int lcm_by_prime_factors(int a, int b) {std::unordered_mapint, int factors_a find_prime_factors(a);std::unordered_mapint, int factors_b find_prime_factors(b);// 合并两个数的质因数取最大次数for (const auto factor_b : factors_b) {factors_a[factor_b.first] std::max(factors_a[factor_b.first], factor_b.second);}// 计算最小公倍数int lcm 1;for (const auto factor : factors_a) {lcm * std::pow(factor.first, factor.second);}return lcm;
}int main() {int a 24;int b 36;std::cout LCM of a and b is: lcm_by_prime_factors(a, b) std::endl;return 0;
}
