素数与指数级数

Question

我有兴趣了解是否可以使用素数指数来压缩数字。在我对此进行研究的过程中，我遇到了几种解决方案，其中之一是创建一系列连续的素数，这些素数仅输出其指数量以弥补重新创建输入数字所需的幂。 [此处][1]链接了一个来源

我写了一个与下面类似的函数。然而，经过测试发现，我的代码对于大量数字来说速度慢得不切实际，因为暴力方法在找到可用于计数的数字时非常耗时，以至于计数需要几个小时。我尝试增加使用的素数系列，但结果不佳。有人可以建议任何方法来改进或解决这个问题吗？或者提供任何不同的选项，以便所有数字都可以使用，无论大小？提高效率和结构？

非常感谢

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 = {}

  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

即使你能找到一种快速分解大整数的方法（无论是肖尔的量子算法还是神奇的经典算法），这也不会提供任何整体压缩。您希望能够压缩的整数 (n) 数量（无论您选择哪个整数）对表示其指数平均所需的位数设置了下限 (log₂ n），等于简单表示二进制 0..n-1 所需的位数。