math/factorize.hpp

• View this file on GitHub
• Last update: 2024-07-03 11:46:21+09:00
• Include: #include "math/factorize.hpp"

Verified with

• verify/aoj/aoj_ntl_1_a.test.cpp

Code

vector<pair<long long, int>> factorize(long long N) {
    assert(0 < N);
    vector<pair<long long, int>> ret;
    for(long long p = 2; p * p <= N; p++) {
        if(N % p != 0) continue;
        int e = 0;
        while(N % p == 0) {
            N /= p;
            e++;
        }
        ret.push_back({p, e});
    }
    if(N != 1) ret.push_back({N, 1});
    return ret;
}

#line 1 "math/factorize.hpp"
vector<pair<long long, int>> factorize(long long N) {
    assert(0 < N);
    vector<pair<long long, int>> ret;
    for(long long p = 2; p * p <= N; p++) {
        if(N % p != 0) continue;
        int e = 0;
        while(N % p == 0) {
            N /= p;
            e++;
        }
        ret.push_back({p, e});
    }
    if(N != 1) ret.push_back({N, 1});
    return ret;
}

Back to top page