若正整数 #{{a}}# 除以正整数 #{{b}}# 可以整除,则称 #{{b}}# 为 #{{a}}# 的因数(Factor),#{{a}}# 为 #{{b}}# 的倍数(Multiple),#{{1}}# 是所有正整数最小的因数,任意正整数最大的因数就是该正整数本身。若 #{{a}}# 同时是 #{{x}}# 和 #{{y}}# 的因数,则称 #{{a}}# 是 #{{x}}# 和 #{{y}}# 的公因数(Common Divisor),如果 #{{a}}# 是 #{{x}}# 和 #{{y}}# 的公因数中最大的一个,则称 #{{a}}# 是 #{{x}}# 和 #{{y}}# 的最大公因数(Greatest Common Divisor,简称 GCD)。若 #{{a}}# 同时是 #{{x}}# 和 #{{y}}# 的倍数,则称 #{{a}}# 是 #{{x}}# 和 #{{y}}# 的公倍数(Common Multiple);如果 #{{a}}# 是 #{{x}}# 和 #{{y}}# 的公倍数中最小的一个,则称 #{{a}}# 是 #{{x}}# 和 #{{y}}# 的最小公倍数(Least Common Multiple,简称 LCM)。
若因数是质数(Prime),则称其为质因数(Prime Factor)。找出一个正整数的所有质因数之行为,就称为「质因数分解」(Prime Factorization)。若要对数值不大的正整数 #{{N}}# 做质因数分解,可以利用试除法(Trial Division),找出 #{{2}}# 到 #{{\sqrt{N}}}# 之间的质数,来一个一个测试 #{{N}}# 是否能够被这个范围的质数整除。如果找不到,那 #{{N}}# 的质因数就是 #{{N}}# 的自身。
pub fn prime_factorize(mut n: i32) -> Vec<i32> {
if n < 2 {
Vec::new()
} else if n <= 3 {
vec![n]
} else {
let mut prime_factors = Vec::new();
let primes = get_prime_numbers(2, (n as f64).sqrt().floor() as i32);
for prime in primes {
while n > 1 && n % prime == 0 {
prime_factors.push(prime);
n /= prime;
}
}
if n > 1 {
prime_factors.push(n);
}
prime_factors
}
}
pub fn get_prime_numbers(mut a: i32, b: i32) -> Vec<i32> {
let mut result = Vec::new();
match a {
0 | 1 => {
if b >= 3 {
result.push(2);
result.push(3);
a = 5;
} else if b == 2 {
result.push(2);
return result;
} else {
return result;
}
}
2 => {
result.push(2);
if b == 2 {
return result;
}
result.push(3);
a = 5;
}
3 => {
result.push(3);
a = 5;
}
x if x % 2 == 0 => {
a += 1;
}
_ => ()
}
'outer: for n in (a..=b).step_by(2) {
let m = n % 6;
if m != 1 && m != 5 {
continue;
}
let n_sqrt = (n as f64).sqrt().floor() as i32;
if n_sqrt >= a {
for i in (5..a).step_by(6) {
if n % i == 0 || n % (i + 2) == 0 { // n % i: 6n + 5 -> 6(n + 1) - 1 -> 6n - 1, n % (i + 2): 6n + 1
continue 'outer;
}
}
for p in result.iter().copied() {
if p > n_sqrt {
break;
}
if n % p == 0 {
continue 'outer;
}
}
} else {
for i in (5..=n_sqrt).step_by(6) {
if n % i == 0 || n % (i + 2) == 0 { // n % i: 6n + 5 -> 6(n + 1) - 1 -> 6n - 1, n % (i + 2): 6n + 1
continue 'outer;
}
}
}
result.push(n);
}
result
}
public static ArrayList<Integer> primeFactorize(int n) {
if (n < 2) {
return new ArrayList<>();
} else if (n <= 3) {
final ArrayList<Integer> primeFactor = new ArrayList<>(1);
primeFactor.add(n);
return primeFactor;
} else {
final ArrayList<Integer> primeFactors = new ArrayList<>();
final ArrayList<Integer> primes = getPrimeNumber(2, (int) Math.floor(Math.sqrt(n)));
for (final int prime : primes) {
while (n > 1 && n % prime == 0) {
primeFactors.add(prime);
n /= prime;
}
}
if (n > 1) {
primeFactors.add(n);
}
return primeFactors;
}
}
public static ArrayList<Integer> getPrimeNumber(int a, final int b) {
final ArrayList<Integer> result = new ArrayList<>();
switch (a) {
case 0:
case 1:
if (b >= 3) {
result.add(2);
result.add(3);
a = 5;
} else if (b == 2) {
result.add(2);
return result;
} else {
return result;
}
break;
case 2:
result.add(2);
if (b == 2) {
return result;
}
result.add(3);
a = 5;
break;
case 3:
result.add(3);
a = 5;
break;
default:
if (a % 2 == 0) {
++a;
}
}
outer:
for (int n = a; n <= b; n += 2) {
final int m = n % 6;
if (m != 1 && m != 5) {
continue;
}
final int nSqrt = (int) Math.floor(Math.sqrt(n));
if (nSqrt >= a) {
for (int i = 5; i < a; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) { // n % i: 6n + 5 -> 6(n + 1) - 1 -> 6n - 1, n % (i + 2): 6n + 1
continue outer;
}
}
for (final int p : result) {
if (p > nSqrt) {
break;
}
if (n % p == 0) {
continue outer;
}
}
} else {
for (int i = 5; i <= nSqrt; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) { // n % i: 6n + 5 -> 6(n + 1) - 1 -> 6n - 1, n % (i + 2): 6n + 1
continue outer;
}
}
}
result.add(n);
}
return result;
}
function primeFactorize(n: number) {
if (n < 2) {
return [];
} else if (n <= 3) {
return [n];
} else {
const primeFactors = [];
const primes = getPrimeNumber(2, Math.floor(Math.sqrt(n)));
for (const prime of primes) {
while (n > 1 && n % prime === 0) {
primeFactors.push(prime);
n /= prime;
}
}
if (n > 1) {
primeFactors.push(n);
}
return primeFactors;
}
}
function getPrimeNumber(a: number, b: number) {
const result: number[] = [];
switch (a) {
case 0:
case 1:
if (b >= 3) {
result.push(2);
result.push(3);
a = 5;
} else if (b === 2) {
result.push(2);
return result;
} else {
return result;
}
break;
case 2:
result.push(2);
if (b === 2) {
return result;
}
result.push(3);
a = 5;
break;
case 3:
result.push(3);
a = 5;
break;
default:
if (a % 2 === 0) {
a += 1;
}
}
if (a < 2 && b >= 2) {
result.push(2);
a = 3;
} else if (a % 2 === 0) {
if (a === 2) {
result.push(2);
}
a += 1;
}
outer:
for (let n = a;n <= b;n += 2) {
const m = n % 6;
if (m !== 1 && m !== 5) {
continue;
}
const nSqrt = Math.floor(Math.sqrt(n));
if (nSqrt >= a) {
for (let i = 5;i < a;i += 6) {
if (n % i === 0 || n % (i + 2) === 0) { // n % i: 6n + 5 -> 6(n + 1) - 1 -> 6n - 1, n % (i + 2): 6n + 1
continue outer;
}
}
for (const p of result) {
if (p > nSqrt) {
break;
}
if (n % p === 0) {
continue outer;
}
}
} else {
for (let i = 5;i <= nSqrt;i += 6) {
if (n % i === 0 || n % (i + 2) === 0) { // n % i: 6n + 5 -> 6(n + 1) - 1 -> 6n - 1, n % (i + 2): 6n + 1
continue outer;
}
}
}
result.push(n);
}
return result;
}
func PrimeFactorize(n int) []int {
if n < 2 {
return []int{}
} else if n <= 3 {
return []int{n}
} else {
primeFactors := make([]int, 0)
primes := GetPrimeNumber(2, int(math.Floor(math.Sqrt(float64(n)))))
for _, prime := range primes {
for n > 1 && n%prime == 0 {
primeFactors = append(primeFactors, prime)
n /= prime
}
}
if n > 1 {
primeFactors = append(primeFactors, n)
}
return primeFactors
}
}
func GetPrimeNumber(a int, b int) []int {
result := make([]int, 0)
switch a {
case 0, 1:
if b >= 3 {
result = append(result, 2)
result = append(result, 3)
a = 5
} else if b == 2 {
result = append(result, 2)
return result
} else {
return result
}
case 2:
result = append(result, 2)
if b == 2 {
return result
}
result = append(result, 3)
a = 5
case 3:
result = append(result, 3)
a = 5
default:
if a%2 == 0 {
a++
}
}
outer:
for n := a; n <= b; n += 2 {
m := n % 6
if m != 1 && m != 5 {
continue
}
nSqrt := int(math.Floor(math.Sqrt(float64(n))))
if nSqrt >= a {
for i := 5; i < a; i += 6 {
if n%i == 0 || n%(i+2) == 0 { // n % i: 6n + 5 -> 6(n + 1) - 1 -> 6n - 1, n % (i + 2): 6n + 1
continue outer
}
}
for _, p := range result {
if p > nSqrt {
break
}
if n%p == 0 {
continue outer
}
}
} else {
for i := 5; i <= nSqrt; i += 6 {
if n%i == 0 || n%(i+2) == 0 { // n % i: 6n + 5 -> 6(n + 1) - 1 -> 6n - 1, n % (i + 2): 6n + 1
continue outer
}
}
}
result = append(result, n)
}
return result
}
要求两正整数 #{{a}}#、#{{b}}# 的最大公因数,可以利用上面介绍的方式找出两数的所有质因数,再把所有共同的质因数相乘,积就是最大公因数了(短除法的应用)……不过这样做其实挺慢的,以下介绍用辗转相除法求最大公因数的方式,会快很多。
辗转相除法又称欧几里得算法(Euclidean algorithm),相信这个大家在中学阶段都用得吓吓叫了,这边就不再多提。简而言之,要用辗转相除法取得两正整数的最大公因数,那就是把这两数以大除小相除,取余数后,把余数当作原本除数的除数,再进行一次除法。取余数后,再把这个余数当作除数,去除前一个余数,如此反复,直到余数为 0 时,前一个除数就是最大公因数。
pub fn gcd(mut a: i32, mut b: i32) -> i32 {
if b > a {
swap(&mut a, &mut b);
}
let mut m = a % b;
while m != 0 {
a = b;
b = m;
m = a % b;
}
b
}
public static int gcd(int a, int b) {
if (b > a) {
final int c = b;
b= a;
a = c;
}
int m = a % b;
while(m != 0){
a = b;
b = m;
m = a % b;
}
return b;
}
function gcd(a: number, b: number) {
if (b > a) {
const c = b;
b = a;
a = c;
}
let m = a % b;
while (m !== 0) {
a = b;
b = m;
m = a % b;
}
return b;
}
func Gcd(a int, b int) int {
if b > a {
c := b
b = a
a = c
}
m := a % b
for m != 0 {
a = b
b = m
m = a % b
}
return b
}
对于不擅长处理除法的 CPU,可以改用斯泰因算法(Stein's algorithm),又称为二元 GCD 算法(Binary GCD algorithm)。这个算法是根据以下四个事实来求最大公因数的:
pub fn gcd(a: usize, b: usize) -> usize {
if a == b || b == 0 {
a
} else if a == 0 {
b
} else if a & 1 == 0 {
if b & 1 == 0 {
gcd(a >> 1, b >> 1) << 1
} else {
gcd(a >> 1, b)
}
} else if b & 1 == 0 {
gcd(a, b >> 1)
} else if a > b {
gcd((a - b) >> 1, b)
} else {
gcd(a, (b - a) >> 1)
}
}
public static int gcd(int a, int b) {
if (a == b || b == 0) {
return a;
} else if (a == 0) {
return b;
} else if ((a & 1) == 0) {
if ((b & 1) == 0) {
return gcd(a >> 1, b >> 1) << 1;
} else {
return gcd(a >> 1, b);
}
} else if ((b & 1) == 0) {
return gcd(a, b >> 1);
} else if (a > b) {
return gcd((a - b) >> 1, b);
} else {
return gcd(a, (b - a) >> 1);
}
}
function gcd(a: number, b: number): number {
if (a === b || b === 0) {
return a;
} else if (a === 0) {
return b;
} else if ((a & 1) === 0) {
if ((b & 1) === 0) {
return gcd(a >> 1, b >> 1) << 1;
} else {
return gcd(a >> 1, b);
}
} else if ((b & 1) === 0) {
return gcd(a, b >> 1);
} else if (a > b) {
return gcd((a - b) >> 1, b);
} else {
return gcd(a, (b - a) >> 1);
}
}
func Gcd(a int, b int) int {
if a == b || b == 0 {
return a
} else if a == 0 {
return b
} else if a&1 == 0 {
if b&1 == 0 {
return Gcd(a>>1, b>>1) << 1
} else {
return Gcd(a>>1, b)
}
} else if b&1 == 0 {
return Gcd(a, b>>1)
} else if a > b {
return Gcd((a-b)>>1, b)
} else {
return Gcd(a, (b-a)>>1)
}
}
pub fn gcd(mut a: usize, mut b: usize) -> usize {
let mut two_counter = 0;
loop {
if a == b || b == 0 {
return a << two_counter;
} else if a == 0 {
return b << two_counter;
} else if a & 1 == 0 {
a >>= 1;
if b & 1 == 0 {
b >>= 1;
two_counter += 1;
}
} else if b & 1 == 0 {
b >>= 1;
} else if a > b {
a = (a - b) >> 1;
} else {
b = (b - a) >> 1;
}
}
}
public static int gcd(int a, int b) {
int twoCounter = 0;
while (true) {
if (a == b || b == 0) {
return a << twoCounter;
} else if (a == 0) {
return b << twoCounter;
} else if ((a & 1) == 0) {
a >>= 1;
if ((b & 1) == 0) {
b >>= 1;
twoCounter += 1;
}
} else if ((b & 1) == 0) {
b >>= 1;
} else if (a > b) {
a = (a - b) >> 1;
} else {
b = (b - a) >> 1;
}
}
}
function gcd(a: number, b: number) {
let twoCounter = 0;
for (; ;) {
if (a === b || b === 0) {
return a << twoCounter;
} else if (a === 0) {
return b << twoCounter;
} else if ((a & 1) === 0) {
a >>= 1;
if ((b & 1) === 0) {
b >>= 1;
twoCounter += 1;
}
} else if ((b & 1) === 0) {
b >>= 1;
} else if (a > b) {
a = (a - b) >> 1;
} else {
b = (b - a) >> 1;
}
}
}
func Gcd(a int, b int) int {
var twoCounter uint
for {
if a == b || b == 0 {
return a << twoCounter
} else if a == 0 {
return b << twoCounter
} else if a&1 == 0 {
a >>= 1
if b&1 == 0 {
b >>= 1
twoCounter += 1
}
} else if b&1 == 0 {
b >>= 1
} else if a > b {
a = (a - b) >> 1
} else {
b = (b - a) >> 1
}
}
}
pub fn lcm(a: i32, b: i32) -> i32 {
a * b / gcd(a, b)
}
pub fn gcd(mut a: i32, mut b: i32) -> i32 {
if b > a {
swap(&mut a, &mut b);
}
let mut m = a % b;
while m != 0 {
a = b;
b = m;
m = a % b;
}
b
}
public static int lcm(int a, int b) {
return a * b / gcd(a, b);
}
public static int gcd(int a, int b) {
if (b > a) {
final int c = b;
b= a;
a = c;
}
int m = a % b;
while(m != 0){
a = b;
b = m;
m = a % b;
}
return b;
}
function lcm(a: number, b: number) {
return a * b / gcd(a, b);
}
function gcd(a: number, b: number) {
if (b > a) {
const c = b;
b = a;
a = c;
}
let m = a % b;
while (m !== 0) {
a = b;
b = m;
m = a % b;
}
return b;
}
func Lcm(a int, b int) int {
return a * b / Gcd(a, b)
}
func Gcd(a int, b int) int {
if b > a {
c := b
b = a
a = c
}
m := a % b
for m != 0 {
a = b
b = m
m = a % b
}
return b
}