C/C++刷题中的数学问题（公因数、公倍数、质数等）

公因数、公倍数、质数等）"/>

C/C++刷题中的数学问题（公因数、公倍数、质数等）

公倍数和公因数

利用辗转相除法，我们可以很方便地求得两个数的最大公因数（greatest common divisor，gcd）；将两个数相乘再除以最大公因数即可得到最小公倍数（least common multiple, lcm）。

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

进一步地，我们也可以通过扩展欧几里得算法（extended gcd）在求得 a 和 b 最大公因数的同时，也得到它们的系数 x 和 y，从而使 ax + by = gcd(a, b)。

int xGCD(int a, int b, int &x, int &y) {if (!b) {x = 1, y = 0;return a;}int x1, y1, gcd = xGCD(b, a % b, x1, y1);x = y1, y = x1 - (a / b) * y1;return gcd;
}

质数

204.计数质数

题目描述

给定一个数字 n，求小于 n 的质数的个数。

输入输出样例

输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

题解
埃拉托斯特尼筛法（Sieve of Eratosthenes，简称埃氏筛法）是非常常用的，判断一个整数是否是质数的方法。并且它可以在判断一个整数 n 时，同时判断所小于 n 的整数，因此非常适合这道题。其原理也十分易懂：从 1 到 n 遍历，假设当前遍历到 m，则把所有小于 n 的、且是 m 的倍数的整数标为和数；遍历完成后，没有被标为和数的数字即为质数。

代码

class Solution {
public:int countPrimes(int n) {vector<int> isPrime(n, 1);int ans = 0;for (int i = 2; i < n; ++i) {if (isPrime[i]) {ans += 1;if ((long long)i * i < n) {for (int j = i * i; j < n; j += i) {isPrime[j] = 0;}}}}return ans;}
};

数字处理

504.七进制数

题目描述

给定一个整数 num，将其转化为 7 进制，并以字符串形式输出。

输入输出样例

输入: num = 100
输出: "202"

代码

class Solution {
public:string convertToBase7(int num) {if(num==0) return "0";bool is_negative=num<0;if(is_negative) num=-num;string ans;while(num){int a=num/7,b=num%7;ans=to_string(b)+ans;num=a;}return is_negative?"-"+ans:ans;}
};

172.阶乘后的零

题目描述

给定一个整数 n ，返回 n! 结果中尾随零的数量。

提示 n! = n * (n - 1) * (n - 2) * … * 3 * 2 * 1

输入输出样例

输入：n = 3
输出：0
解释：3! = 6 ，不含尾随 0

题解

每个尾部的 0 由 2 × 5 = 10 而来，因此我们可以把阶乘的每一个元素拆成质数相乘，统计有多少个 2 和 5。明显的，质因子 2 的数量远多于质因子 5 的数量，因此我们可以只统计阶乘结果里有多少个质因子 5。

代码

class Solution {
public:int trailingZeroes(int n) {return n==0?0:n/5+trailingZeroes(n/5);}
};

326.3的幂

题目描述

判断一个数字是否是 3 的次方。

输入输出样例

输入：n = 27
输出：true

代码

利用对数

class Solution {
public:bool isPowerOfThree(int n) {return fmod(log10(n) / log10(3), 1) == 0;}
};

因为在 int 范围内 3 的最大次方是 1162261467，如果 n 是 3 的整数次方，那么 1162261467 除以 n 的余数一定是零；

class Solution {
public:bool isPowerOfThree(int n) {return n > 0 && 1162261467 % n == 0;}
};