Python 質因數分解 ( Python: Prime Factorization )

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

此文為延續 Python 找質數 一文，在解此題之前，請先看質因數分解的影片講解。

要解這題，有幾種作法：

方法一：

1. 除數從 2 開始，若此被除數可以被除數 2 整除，就被除數就一直除以 2；若不行除數換用 3。

2. 一直重複到 除數的平方大於或小於 被除數。

	def prime_factoring(n):
	divisor = 2
	factors = []
	while divisor * divisor <= n:
	if n % divisor:
	divisor += 1
	else:
	n //= divisor
	factors.append(divisor)
	if n > 1:
	factors.append(n)
	return factors
	aNumber = (int)(input("Enter a number:"));
	print(prime_factoring(aNumber));

view raw PrimeFactoring_V1.py hosted with ❤ by GitHub

方法二：

1. 求出小於此被除數開根號後的所有質數。
2. 在用這些質數去除被除數算出每個質因數出現的次數。

	import math;
	def eratosthenes(n):
	P = [i for i in range(2, (int)(math.sqrt(n)+1))]
	p = 0
	while True:
	for i in P[p + 1:]:
	if i % P[p] == 0:
	P.remove(i)
	if P[p]**2 >= P[-1]:
	break
	p += 1
	return P
	aNumber = (int)(input("Enter a number:"));
	factors = eratosthenes(aNumber);
	num = aNumber;
	for divisor in factors:
	while( num % divisor == 0 ):
	num //= divisor
	print(divisor, ' ', end = '');

view raw PrimeFactoring_V2.py hosted with ❤ by GitHub

方法二好像不怎麼好XD。

除了以上方法外，讀者您還有想到什麼方法呢？