cplib/math/primefactor.nim

• View this file on GitHub
• Last update: 2024-11-07 17:54:13+09:00

Depends on

• cplib/math/inner_math.nim
• cplib/math/inner_math.nim
• cplib/math/isprime.nim
• cplib/math/isprime.nim
• cplib/math/powmod.nim
• cplib/math/powmod.nim
• cplib/str/run_length_encode.nim
• cplib/str/run_length_encode.nim

Required by

• cplib/math/divisor.nim
• cplib/math/divisor.nim
• cplib/math/primitive_root.nim
• cplib/math/primitive_root.nim
• verify/math/divisor_atcoder_test_.nim
• verify/math/divisor_atcoder_test_.nim
• verify/math/divisor_many_atcoder_test_.nim
• verify/math/divisor_many_atcoder_test_.nim
• verify/math/factorize_table_abc284d_test_.nim
• verify/math/factorize_table_abc284d_test_.nim
• verify/math/factorize_tuple_abc324b_test_.nim
• verify/math/factorize_tuple_abc324b_test_.nim

Verified with

• verify/math/euler_phi_yukicoder_test.nim
• verify/math/euler_phi_yukicoder_test.nim
• verify/math/factorize_yosupo_test.nim
• verify/math/factorize_yosupo_test.nim

Code

when not declared CPLIB_MATH_PRIMEFACTOR:
    const CPLIB_MATH_PRIMEFACTOR* = 1
    import cplib/math/inner_math
    import cplib/math/isprime
    import cplib/str/run_length_encode
    import random, std/math, algorithm, tables

    randomize()
    proc find_factor(n: int): int =
        if not ((n and 1) != 0): return 2
        if isprime(n): return n
        const m = 128
        while true:
            var x, ys, q, r, g = 1
            var rnd, y = rand(0..n-3) + 2
            proc f(x: int): int = add(mul(x, x, n), rnd, n)
            while g == 1:
                x = y
                for i in 0..<r: y = f(y)
                for k in countup(0, r-1, m):
                    ys = y
                    for _ in 0..<min(m, r-k):
                        y = f(y)
                        q = mul(q, abs(x-y), n)
                    g = gcd(q, n)
                    if g != 1: break
                r = r shl 1
            if g == n:
                g = 1
                while g == 1:
                    ys = f(ys)
                    g = gcd(n, abs(x - ys))
            if g < n:
                if isprime(g): return g
                elif isprime(n div g): return n div g
                return find_factor(g)

    proc primefactor*(n: int, sorted: bool = true): seq[int] =
        var n = n
        while n > 1 and not isprime(n):
            var p = find_factor(n)
            while n mod p == 0:
                result.add(p)
                n = n div p
        if n > 1: result.add(n)
        if sorted: return result.sorted

    proc primefactor_table*(n: int): Table[int, int] =
        for p in primefactor(n):
            if p in result: result[p] += 1
            else: result[p] = 1

    proc primefactor_tuple*(n: int): seq[(int, int)] = primefactor(n, true).run_length_encode

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/onlinejudge_verify/languages/nim.py", line 86, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page