Primes with exponent series

Question

I was interested in finding out if I could compact a number using prime exponents. During my research into this, I came across several solutions one being the creation of a sequential series of primes that only output their exponent amounts to make up the powers needed to recreate the inputted number. One source is linked [here][1]

I have written a function similar to this below. However, upon testing have found out my code is unrealistically slow for large numbers as the brute force approach is time-consuming in finding a number that can be used to the point where the count takes hours. I have tried increasing the prime series used with poor outcomes. Can someone suggest any way to improve or solve this issue? Or offer any different options so all numbers can be used no matter the size? improved efficiencies and structure?

Many thanks

def get_primes(n):
primes = []
num = 2

while len(primes) < n:
    is_prime = all(num % i != 0 for i in range(2, int(num**0.5) + 1))
    if is_prime:
        primes.append(num)
    num += 1

return primes

def get_max_prime_amount(num):
  result = num // 3  # Use integer division for max_prime
  return result

def factorize_with_errors(original_number, primes, max_prime):
  error_count = 0
  soriginal_number = original_number
  tCount = 0
  PrimeArray = {}
  ExponentArray = {}

  for tPrimeCount in primes:
      tCount += 1
      PrimeArray[tCount] = tPrimeCount
      ExponentArray[tCount] = 0

  max_prime_number = PrimeArray[tCount]
  tCurrentPrimeCount = 1
  tFactorisation = False

  while not tFactorisation:
          if error_count == 99999999:
              breakpoint()

          tQuotient = gmpy2.mpfr(gmpy2.div(original_number,PrimeArray[tCurrentPrimeCount]))

        if tQuotient.is_integer():
            ExponentArray[tCurrentPrimeCount] += 1

            if tQuotient > max_prime_number:
                if tCurrentPrimeCount == max_prime:
                    tCurrentPrimeCount = 1
                    error_count += 1
                    original_number = int(tQuotient) - 1
                else:
                    original_number = int(tQuotient)
            elif tQuotient <= max_prime_number:
                if tQuotient == 1:
                    tFactorisation = True
                elif tQuotient in primes:
                    for tKey in PrimeArray:
                        if PrimeArray[tKey] == tQuotient:
                            ExponentArray[tKey] += 1
                            tFactorisation = True
                            break
                elif tQuotient not in primes:
                    tCurrentPrimeCount = 1
                    FinalFactorisation = False
                    while not FinalFactorisation:
                        tQuotientNew = tQuotient / PrimeArray[tCurrentPrimeCount]

                        if tQuotientNew == 1:
                            ExponentArray[tCurrentPrimeCount] += 1
                            tQuotient = tQuotientNew
                            tFactorisation = True
                            break
                        elif tQuotientNew.is_integer():
                            ExponentArray[tCurrentPrimeCount] += 1
                            tQuotient = tQuotientNew
                            break
                        else:
                            tCurrentPrimeCount += 1
                break

        elif not tQuotient.is_integer():
            if tCurrentPrimeCount == max_prime:
                tCurrentPrimeCount = 1
                error_count += 1
                soriginal_number -= 1
                original_number = soriginal_number
                for sKey in ExponentArray:
                    ExponentArray[sKey] = 0
            elif tCurrentPrimeCount < max_prime:
                tCurrentPrimeCount += 1

ExponentArray["error_count"] = error_count
return ExponentArray



original_number = 288684097887703
input_amount_len = len(str(original_number))
max_prime = get_max_prime_amount(input_amount_len)
primes = get_primes(max_prime)
result = factorize_with_errors(original_number, primes, max_prime)
print(result)

[1]: https://patentimages.storage.googleapis.com/65/24/94/5733e3b760d3e3/US6373986.pdf

Answer 1

Even if you could find a way to factor large integers quickly (be it Shor's quantum algorithm or a miraculous classical algorithm), this would not provide any overall compression. The number of integers (n) that you want to be able to compress (regardless of which integers you pick) puts a lower bound on the number of bits that will be needed on average to represent their exponents (log₂n), which is equal to the number of bits needed to simply represent 0..n-1 in binary.