コード

vector<uint64_t> prime_factor(uint64_t n) {
    vector<array<uint64_t, 2>> ret;
    for (uint64_t i = 2; i * i <= n; ++i) {
        if (n % i) continue;
        uint64_t cnt = 0;
        while (n % i == 0) {
            n /= i;
            ++cnt;
        }
        ret.push_back({ i, cnt });
    }
    if (n != 1) ret.push_back({ n, 1 });
    return ret;
}

解説のようなもの

for (uint64_t i = 2; i * i <= n; ++i)

まず、ある整数 $N$ が合成数の時からなず $\sqrt{N}$ 以下に約数が存在します。
$i \leq \sqrt{N} = i \times i \leq N$ です。
このfor文では最小の素数である2から、調べる必要のある最大の約数までを探索します。( $\sqrt{N}$ 以降は対称性により必要ありません)

if (n % i) continue;

ここでは素数以外、またはnの約数に存在しない素数をはじいています。
このif文を通過するiはすべて素数です。なぜでしょうか？

まず、ある合成数 $N$ の素因数はすべて $N$ 未満です。
iが合成数の時、iで割り切れる $N$ はiの素因数をすべて持たなければなりません。
しかしながら、 $N$ はiより小さい素数をすべて取り除かれています。

uint64_t cnt = 0;

素数iが $N$ の中にいくつ存在するかを保持しておくための変数です。

while (n % i == 0) {

$N$ をiで割り切れることができる限りループします。

n /= i; ++cnt;

$N$ から素因数iを1つ取り除き、カウント値を1つ増加させます。

ret.push_back({ i, cnt });

素因数iがcnt個存在したことを戻り値用配列に保持させます。

if (n != 1) ret.push_back({ n, 1 });

最後に残った $N$ が素数の時、 $N$ を戻り値用配列に追加します。

すていさんの雑記

sqrt(N)の素因数分解

コード