Day 165-Q5 — 2026-09-29 | 最小の原始根（$p\le10^{12}$ の素数。$p-1$ の素因数ごとの位数判定）

📋 コピーimport sys
def factor_primes(x, primes):
    """x の異なる素因数。primes は sqrt(x) 以上まで"""
    fs = []
    for q in primes:
        if q * q > x: break
        if x % q == 0:
            fs.append(q)
            while x % q == 0: x //= q
    if x > 1: fs.append(x)
    return fs
def main():
    data = sys.stdin.read().split()
    t = int(data[0]); ps = [int(x) for x in data[1:1 + t]]
    lim = 10**6 + 1
    sv = bytearray([1]) * (lim + 1); sv[0:2] = b"\x00\x00"
    for i in range(2, int(lim ** 0.5) + 1):
        if sv[i]: sv[i * i::i] = bytearray(len(sv[i * i::i]))
    primes = [i for i in range(2, lim + 1) if sv[i]]
    out = []
    for p in ps:
        if p == 2: out.append(1); continue
        qs = factor_primes(p - 1, primes)
        g = 2
        while True:
            # g が原始根 <=> 各素因数 q で g^((p-1)/q) != 1 (mod p)
            if all(pow(g, (p - 1) // q, p) != 1 for q in qs): break
            g += 1
        out.append(g)
    print("\n".join(map(str, out)))
main()