埃氏篩＋歐拉篩求素數
- 前言
- 一 埃氏篩篩＋模板
- 二 歐拉篩＋模板
- 三 每日共勉
前言
對于求解1-n區間內的所有素數，如果一個個判斷的話可能會超時，這里介紹一下歐拉篩，用于求解一段區域里邊的素數，
通常我們會用埃式篩或者歐拉篩，同時對于其他用到素數的，通常都會先篩個素數陣列出來，
一 埃氏篩篩＋模板
埃拉托斯特尼篩法，簡稱埃氏篩，
埃式篩思想通俗易懂，適合新手使用，很容易想起來，
但是缺點是計算冗余，多次重復計算，
由整數分解定理，一個整數一定能被分解為幾個（或者素數為一個）質數的冪的乘積，并且這個數的質因子一定是小于它本身的，所以當我們從小到大將每個質數的倍數都篩去的話，其后在遍歷到一個非素數時，它一定已經被它的質因子給篩去了，
#include<cstdio>
using namespace std;
const int N = 1e7 + 5;
int st[N];
void aishi(int n){
for(int i = 2; i <= n; i++)
{
if(st[i] == 0)
{
for(int j = 2 * i; j <= n; j += i)
st[j] = 1; // j是i的一個倍數，j是合數，篩掉，
}
}
}
二 歐拉篩＋模板
歐拉篩時間復雜度O（n），所以歐拉篩又稱線性篩，
1.prime[N]記錄素數
2.vis[N]標記是不是素數，
注意陳述句if(i % prime[j] == 0) break; //如果能被除盡就break，保證每個數只被它最小素因子篩去，
從而達到防止重復計算，
#include<cstdio>
using namespace std;
const int maxn = 1e7 + 5;
int prime[maxn];
bool vis[maxn];
void oula(int n)
{
int cnt = 0;
for(int i = 2; i <= n; i++)
{
if(!vis[i]) //vis為0是素數
prime[cnt++] = i; //找到素數
for(int j = 0; j < cnt && i * prime[j] <= n; j++)
{
vis[i * prime[j]] = true; //篩掉非素
if(i % prime[j] == 0) break; //如果能被除盡就break，
}
}
}
三 每日共勉
梅雪爭春未肯降，騷人擱筆費評章，
梅須遜雪三分白，雪卻輸梅一段香，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/272000.html
標籤：其他
上一篇：JavaScript陣列方法總結
下一篇：vue怎么封裝和呼叫公共方法