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

自然数 a と b が a >= b ならば a = p*b + q (b > q) となる整数 p と q が存在します。b を割り切る整数 (b の約数) のうち q を割り切る整数 (b と q の公約数) ならば a も割り切ります。また a と b の最大公約数が 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;
}

値の非常に大きい整数 a と b について、区間 [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