大整數的因數分解

#

# 測試由 BARD 提供的因數分解的 Python 程式

#

# 8976543213214567897654321987123456789111 =

# 60337 *

# 148773442716982413737082088720411303

#

def sieve_of_eratosthenes(n):

  """

  使用Eratosthenes篩選法找出1到n之間的所有素數。

  Args:    n:  要找的素數上限。

  Returns:    一個包含1到n之間所有素數的列表。

  """

  primes = []

  is_prime = [True] * (n + 1)

  is_prime[0] = False

  is_prime[1] = False

  for i in range(2, n + 1):

    if is_prime[i]:

      primes.append(i)

      for j in range(i * 2, n + 1, i):

        is_prime[j] = False

  return primes

def factorize(n):

  """

  使用二次篩選法找出n的所有質因數。

  Args:    n:  要分解的整數。

  Returns:    一個包含n的所有質因數的列表。

  """

  factors = []

  for prime in primes:

    while n % prime == 0:

      factors.append(prime)

      n //= prime

  if n > 1:

    factors.append(n)

  return factors

if __name__ == "__main__":

  n = int(input("請輸入一個整數："))

  factors = factorize(n)

  print("{} 的質因數為：".format(n))

  for factor in factors:

    print(factor)