# 素數及其應用 ## 素數判斷 ```c++ // 用 sqrt 函數 bool isPrime(int n){ if(n<=1) return false; int sqr=(int)sqrt(1.0*n); for(int i=2;i<=sqr;i++){ if(n%i==0) return false; } return true; } // 更簡潔寫法 bool isPrime(int n){ if(n<=1) return false; for(int i=2;i*i<=n;i++){ if(n%i==0) return false; } return true; } ``` ## 素數表獲取 - 素數表的獲取一種是逐個判斷是否為素數，復雜度為 O(n√n) - 還有一種是埃式（Eratosthenes）篩法，復雜度為 O(nloglogn) ```C++ const int maxn=101; // 范圍限定為100以內 int prime[maxn], pnum=0; bool p[maxn]={0}; void findPrime(){ for(int i=2;i<maxn;i++){ if(p[i]==false){ prime[pnum++]=i; for(int j=i+i;j<maxn;j+=i){ p[j]=true; } } } } ``` ## 質因子分解 可對每個質因子計算其階數，設質因子 $$p_i$$ 的階數為 $$e_i$$ ，共有 n 個質因子，則 - 因子個數為 $$\Pi_{i=1}^n e_i$$ - 所有因子的和為 $$\Pi_{i=1}^n (1+p_i+\cdots +p_i^{e_i})=\Pi_{i=1}^n \frac{1-p_i^{e_i+1}}{1-p_i}$$ ## ChangeLog > 2018.09.04 初稿