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