C++ 质数分解和异或运算：高效算法实现

#include #include #include #include

const int maxn = 100000008;

std::vector prm, pre; // pre is the min-factor array. bool np[maxn];

void getPrime(const int N = 100000000) { pre.resize(N + 1); for (int i = 2; i <= N; ++i) { if (!np[i]) { prm.push_back(i); pre[i] = i; } for (auto p : prm) if (i * p <= N) { int k = i * p; np[k] = true; pre[k] = p; if (i % p == 0) break; } else break; } }

int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); getPrime(); int T, n; for (std::cin >> T; T; --T) { std::cin >> n; int ans = 0; while (n != 1) { ans ^= pre[n]; n /= pre[n]; } std::cout << ans << '\n'; } }//转换为PHP内容：<?php

const maxn = 100000008;

function getPrime($N = 100000000) { $pre = array(); $prm = array(); $np = array();

for ($i = 2; $i <= $N; ++$i) { if (!$np[$i]) { array_push($prm, $i); $pre[$i] = $i; } foreach ($prm as $p) { if ($i * $p <= $N) { $k = $i * $p; $np[$k] = true; $pre[$k] = $p; if ($i % $p == 0) { break; } } else { break; } } } return array($prm, $pre); }

list($prm, $pre) = getPrime();

$T = intval(fgets(STDIN)); for ($i = 0; $i < $T; ++$i) { $n = intval(fgets(STDIN)); $ans = 0; while ($n != 1) { $ans ^= $pre[$n]; $n /= $pre[$n]; } echo $ans . "\n"; } ?>