モーダルを閉じる工作HardwareHub ロゴ画像

工作HardwareHubは、ロボット工作や電子工作に関する情報やモノが行き交うコミュニティサイトです。さらに詳しく

利用規約プライバシーポリシー に同意したうえでログインしてください。

工作HardwareHub ロゴ画像 (Laptop端末利用時)
工作HardwareHub ロゴ画像 (Mobile端末利用時)

整数問題に関するアルゴリズム

モーダルを閉じる

ステッカーを選択してください

モーダルを閉じる

お支払い内容をご確認ください

購入商品
」ステッカーの表示権
メッセージ
料金
(税込)
決済方法
GooglePayマーク
決済プラットフォーム
確認事項

利用規約をご確認のうえお支払いください

※カード情報はGoogleアカウント内に保存されます。本サイトやStripeには保存されません

※記事の執筆者は購入者のユーザー名を知ることができます

※購入後のキャンセルはできません

作成日作成日
2016/07/10
最終更新最終更新
2018/11/15
記事区分記事区分
一般公開

目次

    物流業界でソフトウェアエンジニアをやっています

    0
    ステッカーを贈るとは?

    最大公約数 (greatest common divisor; gcd)

    自然数 aba >= b ならば a = p*b + q (b > q) となる整数 pq が存在します。b を割り切る整数 (b の約数) のうち q を割り切る整数 (bq の公約数) ならば a も割り切ります。また ab の最大公約数が b を越えることはありません。そのため gcd(a, b) (= gcd(p*b + q, b)gcd(b, q) と等しくなります。a と 0 の最大公約数は a であるため、この再帰は必ず終了します。

    int gcd(int a, int b) {
        if(b == 0) return a;
        return gcd(b, a % b);
    }
    

    素数

    素数を列挙

    エラトステネスの篩を利用すると、整数 N 以下の素数を効率的に列挙できます。

    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    const int MAXN = 1001024;
    
    // 結果を格納する変数
    int prime[MAXN]; // n 以下の素数のうち i 番目の素数
    bool is_prime[MAXN]; // 整数 i が素数であるかどうか
    
    int sieve(int n) {
        int res = 0;
        fill(is_prime, is_prime + MAXN, true);
        is_prime[0] = is_prime[1] = false; // 0 と 1 は素数ではない。
        for(int i = 2; i <= n; ++i) {
            if(!is_prime[i]) continue;
            prime[res++] = i;
            for(int j = 2 * i; j <= n; j += i) is_prime[j] = false; // 素数 i の倍数は素数ではない (ふるい(篩)にかける)
        }
        return res;
    }
    
    int main() {
        int res = sieve(1000000);
        for(int i = 0; i < res; ++i) cout << prime[i] << endl;
        return 0;
    }
    

    値の非常に大きい整数 ab について、区間 [a,b) の素数を列挙するために、エラトステネスの篩をそのまま用いるとメモリが不足します。b-1 の素数判定は b-1 が 2 以上 sqrt(b-1) 以下の整数 (特に素数) で割り切れるかどうかを考えればよいため、[a,b) の素数判定 (篩にかける処理) のためには 2 以上 sqrt(b-1) 以下の素数一覧 (篩) があれば十分ということになります。これを区間篩とよびます。

    #include <iostream>
    #include <algorithm>
    using namespace std;
    typedef long long unsigned int ll;
    
    const ll MAXN = 1001024; // b-a < MAXN, sqrt(b) < MAXN
    
    ll prime[MAXN]; // [a,b) の素数のうち i 番目の素数
    bool is_prime[MAXN]; // 整数 i が素数であるかどうか
    bool is_prime_ab[MAXN]; // 整数 i+a が素数であるかどうか
    
    ll segment_sieve(ll a, ll b) {
        fill(is_prime, is_prime + MAXN, true);
        fill(is_prime_ab, is_prime_ab + MAXN, true);
        for(ll i = 2; i*i <= b-1; ++i) {
            if(!is_prime[i]) continue;
            for(ll j = 2 * i; j*j <= b-1; j += i) is_prime[j] = false; // 素数 i で篩にかける
            for(ll j = a - a%i; j < b; j += i) {
                if(j < a) continue;
                if(is_prime_ab[j-a]) is_prime_ab[j-a] = false; // 素数 i で篩にかける
            }
        }
        ll res = 0;
        for(ll i = a; i < b; ++i) if(is_prime_ab[i-a]) prime[res++] = i;
        return res;
    }
    
    int main() {
        ll res = segment_sieve(22801763489, 22801787297);
        for(ll i = 0; i < res; ++i) cout << prime[i] << endl;
        return 0;
    }
    

    素数であるかどうかの判定

    整数一つに関して判定する場合は、エラトステネスの篩を用いる必要はありません。

    bool is_prime(int n) {
        if(n == 1) return false; // 1 は素数ではない。
        for(int i = 2; i*i <= n; ++i) { // 2 <= i <= sqrt(n) に約数があれば、
            if(n % i == 0) return false; // n は素数ではない
        }
        return true;
    }
    

    ある整数の約数を列挙

    #include <vector>
    
    vector<int> divisors(int n) {
        vector<int> res;
        for(int i = 1; i*i <= n; ++i) {
            if(n % i != 0) continue;
            res.push_back(i);
            if(n/i == i) continue; // 上の行で追加済み。
            res.push_back(n/i);
        }
        return res;
    }
    

    素因数分解

    #include <iostream>
    #include <map>
    using namespace std;
    
    map<int, int> prime_factors(int n) {
        map<int, int> res;
        if(n == 1) { // n=1 の素因数分解は n^1
            res[n] = 1;
            return res;
        }
        for(int i = 2, _n = n; i*i <= _n; ++i) {
            while(n % i == 0) {
                ++res[i]; // 素数i^{res[i]}
                n /= i;
            }
        }
        if(n != 1) res[n] = 1;
        return res;
    }
    
    int main() {
        map<int, int> res = prime_factors(33);
        for(map<int, int>::iterator it = res.begin(), end = res.end(); it != end; ++it) {
            cout << it->first << "^" << it->second << endl;
        }
        return 0;
    }
    

    出力例

    3^1
    11^1
    
    0
    詳細設定を開く/閉じる
    アカウント プロフィール画像 (本文下)

    物流業界でソフトウェアエンジニアをやっています

    記事の執筆者にステッカーを贈る

    有益な情報に対するお礼として、またはコメント欄における質問への返答に対するお礼として、 記事の読者は、執筆者に有料のステッカーを贈ることができます。

    さらに詳しく →
    ステッカーを贈る コンセプト画像

    Feedbacks

    Feedbacks コンセプト画像

      ログインするとコメントを投稿できます。

      関連記事