Primes class to factorize integers.

primes.py

import sys
from math import *

def error(err):
    print("Error:", err)
    sys.exit(0)

def lcm(a, b):
    return a//gcd(a,b)*b

def isqrt(n):
    x = n
    y = (x+1)//2
    while y < x:
        x = y
        y = (x+n//x)//2
    return x

class Primes:
    def __init__(self, _maxn):
        self.maxn = _maxn
        self.pr = []
        self.lp = [0]*(self.maxn+1)
        self.sieve()
        
    def sieve(self):
        maxn = self.maxn
        lp = self.lp
        pr = self.pr
        for i in range(2, maxn+1):
            if lp[i] == 0:
                lp[i] = i
                pr.append(i)
            for j in range(0, len(pr)):
                if pr[j] > lp[i] or i*pr[j] > maxn:
                    break
                lp[i*pr[j]] = pr[j]

    def isprime(self, n, fact=None):
        if n <= self.maxn:
            return self.lp[n] == n
        if fact == None: fact = self.factorize(n)
        return len(fact) == 1 and n in fact and fact[n] == 1

    def factorize_small(self, n):
        lp = self.lp
        factors = {}
        while n > 1:
            f = lp[n]
            power = 0
            while n % f == 0:
                power += 1
                n //= f
            factors[f] = power
        return factors

    def factorize_big(self, n):
        factors = {}
        for k in range(2, isqrt(n)+1):
            if n % k == 0:
                power = 0
                while n % k == 0:
                    power += 1
                    n //= k
                factors[k] = power
        if n > 1:
            factors[n] = 1 # big prime > sqrt(n)
        return factors

    def factorize(self, n):
        if n <= self.maxn:
            return self.factorize_small(n)
        return self.factorize_big(n)

    def dsum(self, n, fact=None):
        if fact == None: fact = self.factorize(n)
        sm = 1
        for p in fact:
            sm *= (p**(fact[p]+1)-1)//(p-1)
        return sm

    def dcount(self, n, fact=None):
        if fact == None: fact = self.factorize(n)
        cnt = 1
        for p in fact:
            cnt *= (fact[p]+1)
        return cnt