# Common multiples and common factors

Using the rolling division method, we can easily obtain the greatest common divisor (gcd) of two numbers; Multiply the two numbers and divide by the greatest common factor to obtain the 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); }

Furthermore, we can also obtain the coefficients x and y of a and B by extending the Euclidean algorithm (extended gcd), so that 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; }

# Prime number

## 204. Count prime

Title Description

Given a number n, find the number of prime numbers less than n.

Input and output samples

Input: n = 10 Output: 4 Explanation: there are 4 prime numbers less than 10, They are two, 3, 5, 7 .

Problem solution

The Sieve of Eratosthenes is a very common method to judge whether an integer is a prime number. And it can judge the integer less than n when judging an integer n, so it is very suitable for this problem. Its principle is also very easy to understand: traverse from 1 to N. assuming that the current traverse reaches m, mark all integers less than N and multiple of m as sums; After traversal, numbers that are not marked as sum are prime numbers.

code

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; } };

# Digital processing

## 504. Hex number

Title Description

Given an integer num, it is converted to binary 7 and output as a string.

Input and output samples

input: num = 100 output: "202"

code

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. Factorial zero

Title Description

Given an integer n, return n! The number of trailing zeros in the result.

Prompt n= n * (n - 1) * (n - 2) * … * 3 * 2 * 1

Input and output samples

Input: n = 3 Output: 0 Explanation: 3! = 6 ，Without trailing 0

Problem solution

Each trailing 0 consists of 2 × 5 = 10, so we can divide each element of factorial into prime numbers and multiply them, and count how many 2 and 5 there are. Obviously, the number of quality factors 2 is much more than that of quality factors 5, so we can only count the number of quality factors 5 in the factorial result.

code

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

## 326.3 power of

Title Description

Determine whether a number is to the power of 3.

Input and output samples

Input: n = 27 Output: true

code

Using logarithm

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

Because in the int range, the maximum power of 3 is 116261467. If n is an integer power of 3, the remainder of 116261467 divided by N must be zero;

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