gistfile1.txt

8462696833
10086647
6857
1
[71, 839, 1471, 6857]
444444444444444444444444444444444444
148148148148148148148148148148148148
21164021164021164021164021164021164
1924001924001924001924001924001924
148000148000148000148000148000148
7789481473692000007789481473692
210526526316000000210526526316
105263263158000000105263263158
35087754386000000035087754386
17543877193000000017543877193
173701754386138614035087893
17543859649140350877193
333666666333333667
999999000001
[2, 2, 2, 3, 3, 7, 11, 13, 19, 37, 101, 9901, 52579, 333667, 999999000001]

int_fact.py

#!/usr/bin/env python3
from math import floor, log
from decimal import Decimal, getcontext


def is_prime(n):
    """Returns True if n is prime."""
    if n == 2:
        return True
    if n == 3:
        return True
    if n % 2 == 0:
        return False
    if n % 3 == 0:
        return False

    i = 5
    w = 2

    while i * i <= n:
        if n % i == 0:
            return False

        i += w
        w = 6 - w

    return True


def sieve(limit):
    l = [True] * limit
    l[0], l[1] = False, False
    for val, is_prime in enumerate(l):
        if not is_prime:
            continue
        for i in range(val**2, limit, val):
            l[i] = False
    primes = [val for val, is_prime in enumerate(l) if is_prime]
    return primes


def int_fact(n):
    factors = []
    remain = n

    def fact_by_lim(lim):
        nonlocal remain, factors
        primes = sieve(lim)
        while True:
            has_fact = False
            for p in primes:
                if remain % p == 0:
                    has_fact = True
                    remain = int(Decimal(remain) / p)
                    print(remain)
                    factors.append(p)
            if not has_fact:
                break

    for exp in range(2, floor(log(n) / log(10))):
        if is_prime(remain):
            factors.append(remain)
            return sorted(factors)
        lim = 10 ** exp
        will_exit = False
        if lim > remain:
            lim = remain
            will_exit = True
        fact_by_lim(lim)
        if will_exit:
            break
        if remain == 1:
            return sorted(factors)

    if is_prime(remain):
        factors.append(remain)
        return sorted(factors)
    fact_by_lim(remain)
    if remain > 1:
        factors.append(remain)
    return sorted(factors)


def main():
    getcontext().prec = 2000
    print(int_fact(600851475143))
    print(int_fact(888888888888888888888888888888888888))


if __name__ == '__main__':
    main()