競プロのライブラリ整理~素因数分解と素数判定~

素因数分解と素数判定を行うライブラリを作成しました。一つ目は試し割り法によるもので素因数分解を行うことができます。二つ目はエラトステネスの篩の初期化をおこなあった後に素因数分解を行うもので素数判定を行うことも可能です。

使用する際は、こちらのテンプレートと一緒に使ってください。

試し割り法による素因数分解

任意の正の整数について素因数分解した結果を$O(\sqrt{n})$でvectorまたはmapに挿入します¹。

PFvec.cc

class PFvec{
public:
    //PNs:=(素因数分解で出てくる素数を昇順に格納したvector)
    vector<ll> PNs;
    PFvec(ll n){PF(n);}
    void PF(ll n){
        if(n<=1) return;
        ll l=sqrt(n);
        FOR(i,2,l){
            if(n%i==0){
                PF(i);PF(n/i);return;
            }
        }
        PNs.PB(n);return;
    }
};

PFmap.cc

class PFmap{
public:
    //PNs:=(素因数分解で出てくる素数を(昇順に)格納したmap)
    map<ll,ll> PNs;
    PFmap(ll n){PF(n);}
    void PF(ll n){
        if(n<=1) return;
        ll l=sqrt(n);
        FOR(i,2,l){
            if(n%i==0){
                PF(i);PF(n/i);return;
            }
        }
        PNs[n]++;return;
    }
};

エラトステネスの篩による素因数分解と素数判定²

エラトステネスの篩を$O(n \log{\log{n}})$で初期化し、任意の正の整数について素因数分解した結果を$O(\log{n})$でvectorまたはmapに挿入します¹。

したがって、クエリなどで幾度も素因数分解が要求される場合はこちらのアルゴリズムで素因数分解をする必要があります。

また、下記で$PNch[i]=1$の際は$i$が素数であるとして素数判定を行うこともできます。

ES.cc

//PNch[i]:=(iを割り切る最大の素数)
//但し,iが素数の時はPNch[i]=1,i=0,1の時はPNch[i]=0
vector<ll> PNch;

//n:=素因数分解したい中で最大の値(2以上)
void ES(ll n){
    //素数として初期化
    PNch.assign(n+1,1);
    PNch[0]=0;PNch[1]=0;
    ll l=sqrt(n);
    FOR(i,2,l){
        //ある素数の倍数ならばその素数で割り切れる
        if(PNch[i]==1){
            FOR(j,i,n/i)PNch[j*i]=i;
        }
    }
}

PFvec.cc

class PFvec{
public:
    //PNs:=(素因数分解出てくる素数を昇順に格納したvector)
    vector<ll> PNs;
    PFvec(ll n){PF(n);}
    void PF(ll n){
        if(n<=1) return;
        //nが素数の時
        if(PNch[n]==1){PNs.PB(n);return;}
        //マークされている数は素数
        PNs.PB(PNch[n]);
        //マークされている数でnを割った数
        PF(n/PNch[n]);
    }
};

PFmap.cc

class PFmap{
public:
    //PNs:=(素因数分解出てくる素数を(昇順に)格納したmap)
    map<ll,ll> PNs;
    PFmap(ll n){PF(n);}
    void PF(ll n){
        if(n<=1) return;
        //nが素数の時
        if(PNch[n]==1){PNs[n]++;return;}
        //マークされている数は素数
        PNs[PNch[n]]++;
        //マークされている数でnを割った数
        PF(n/PNch[n]);
    }
};

---

1. 但し、mapは挿入でlogがつきます。 ↩

2. この素因数分解の方法が理解できない場合はABC152の解説動画を見ると良いと思います。 ↩