---
# System prepended metadata

title: 數論

---

---
type : slide
---

# 簡單數論

----

數學是程式中最重要的一部分

---

# gcd(最大公因數)

----

## 輾轉相除法(迴圈)

```cpp=
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}
```

----

## 輾轉相除法(遞迴)

```cpp=
int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
```

----

## 內建gcd函式

```cpp=
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int a = 10,b = 15;
    cout<<__gcd(a,b)<<endl;
}
```

---

# lcm(最小公倍數)

----

## code
```cpp=
int lcm(int a, int b) {
    return (a * b) / __gcd(a, b);
}
```

---


# 快速冪

----

## 作用：快速計算平方數
## 原理：分治法


----


```cpp=
int fastpow(int x, int n){
    if(n == 0) 
        return 1;
    int ans = fastpow(x, n/2);
    if(n % 2 == 0) 
        return ans * ans;
    return ans * ans * x;
}

```

時間複雜度：O(log n)


---


# 判斷質數

----

## 窮舉法-1


```cpp=
bool isprime(int n)
{
	if (n <= 1) return false;

	// 窮舉所有可能的因數
	for (int d=2; d<n; ++d)
		if (n % d == 0)
			return false;
	return true;
}

```
時間複雜度 O(n)

----

## 窮舉法-2

```cpp=
bool isprime(int n)
{
	if (n <= 1) return false;

	// 窮舉小於等於sqrt(n)的因數
	for (int d=2; d*d<=n; ++d)
		if (n % d == 0)
			return false;
	return true;
}

```
時間複雜度 O(sqrt(n))



----


## 6n±1 method

將數字分成 6n 、6n+1 、 6n+2 、 6n+3 、 6n+4 、 6+5，只需要拿 6n+1 和 6n+5 試除。



----

## 6n±1 method

```cpp=
bool isprime(int n) {
	if (n <= 1) return false;
	if (n == 2) return true;
	if (n == 3) return true;

	if (n % 2 == 0) return false;
	if (n % 3 == 0) return false;

	for (int d=5, gap=2; d*d<=n; d+=gap, gap=6-gap)
		if (n % d == 0)
			return false;
	return true;
}

```

----


## Miller–Rabin primality test
結合 square root primality test 與 Fermat primality test 。

----

## 費馬小定理

**若n是質數，a小於n，則aⁿ ≡ a (mod n)。**
**若n是質數，a小於n，a不是零，則aⁿ⁻¹ ≡ 1 (mod n)。**


----

## 平方根測試法

**以質數n為模數，0到n-1之間，只有1與n-1，平方之後等於1。
以質數n為模數，1的平方根一定是1與n-1（即±1）。**




----


## Miller–Rabin primality test




```cpp=
bool miller_rabin(int n)
{
	if (n < 2) return false;

//	srand(time(0));
	int a = rand() % (n-2) + 2;

	int u = n-1, t = 0;
	while (u % 2 == 0) u >>= 1, t++;

	int x = pow(a, u, n);	// x = a ^ u % n;
	if (x == 1 || x == n-1) return true;

	for (int i=0; i<t-1; i++)
	{
		x = mul(x, x, n);	// x = x * x % n;
		if (x == 1) return false;
		if (x == n-1) return true;
	}
	return false;
}

```

---





資料來源：https://web.ntnu.edu.tw/~algo/Prime.html