質數：在大于1的整數中，如果只包含1和本身這兩個約數，那么就是素數
試除法：
時間復雜度 O(sqrt(n))
代碼：
static boolean prime(int n){ if(n < 2) return false; for(int i = 2; i <= n/i; i++){//因為i能被整除，那么n/i肯定也能被n整除 if(n % i == 0) return false; } return true; }
線性歐拉篩：
合數只會被它的最小質因子篩掉
時間復雜度：O（n）
static final int N=; static int prime[]=new int[N]; static boolean vis[]=new boolean[N]; static int cnt=0; static void get_primes(int n){ for(int i=2;i<=n;i++){ if(!vis[i]) prime[cnt++]=i; for(int j=0;j<cnt && prime[j]*i<=n;j++){ vis[i*prime[j]]=true; if(i%prime[j]==0) break;//prime[j]是i的最小質因子，那么prime[j]肯定也是i*prime[j]的最小質因子 } } }
埃式篩法：
時間復雜度： O（n*loglogn）在N=10^6，時間和線性歐拉篩法差不多，但是10^7線性歐拉篩法就快了一倍
一個數為素數，那么它的倍數肯定不是素數
代碼：
static final int N=; static int prime[]=new int[N]; static boolean vis[]=new boolean[N]; static int cnt=0; static void get_primes(int n){ for(int i=2;i<=n;i++){ if(!vis[i]){ vis[i]=true; prime[cnt++]=i; for(int j=i+i;j<=n;j+=i) vis[j]=true; } } }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/95250.html
標籤：其他
上一篇：int long的資料范圍
下一篇：分解質因數（模板）