Prime Factors Kata Analysis

Problem Domain Analysis


Every integer can be expressed as a product of prime numbers. The prime factors of an integer n can be expressed as:

n = f1 * f2 * f3 * .... fk

The elements f1, f2, ... fk are all prime factors.

Examples

8 = 2 . 2 . 2
12 = 2 . 2 . 3
18 = 2 . 3 . 3
20 = 2 . 2 . 5
60 = 2 . 2 . 3 . 5

Solution Domain Analysis


Start with the divisor 2 and repeatedly reduce n by a factor of 2 until 2 is no longer an exact divisor. We then try 3 as a divisor and again repeat the reduction process and so on until n has been reduced to 1.

Consider n = 60 :

Marking with an * the unsuccessful attempts to divide, we have:

2   2   2   3   3   4   5
60 30  15* 15   5*  5*  5  1

alt text

Observations

  1. 2 is the only even number that we need to try.
  2. By definition only prime numbers should be considered as candidate divisors.
  3. Generation of a set of prime numbers is an integral part of our algorithm. From our previous discussion on primes, we know that all prime factors of n must be <= square root of n. This suggests a better strategy: Compute prime divisors as they are needed. For this purpose we can include a modified version of the Sieve of Eratosthenes.
  4. As soon as we have discovered n is prime we can terminate.

Pseudo Code

while it has not been established that n is prime do
  a) if current_prime is divisor of n, then save current_prime as a factor and reduce n by current_prime else get next value for the current_prime.
  b) Try current_prime as a divisor of n
end

We now must work out how the 'not prime' test for our outer loop should be implemented. The technique used earlier : to use integer division and test for 0 remainder can be used. We also know that as soon as the prime divisor we are using in our test becomes > square root of n, the process can terminate.

Initially when the prime divisors we are using are much < square root of n, we know that the testing must continue. In carrying out this process, we want to avoid having to calculate square root of n repeatedly. Each time we make the division n div currentprime (eg., 60 div 2) we know the process must continue until the quotient q resulting from the division is < currentprime. At this point we will have:

(current_prime)squared > n 

which will indicate that n is prime. The conditions for it not yet being established that n is prime are therefore:

a) Exact division (ie., r = n modulo current_prime = 0)
b) quotient > divisor (ie., q = n modulo current_prime > current_prime)

The truth of either condition is sufficient to require that the test be repeated again.

Now we need to explore how the algorithm will terminate. If we follow the factorization process through for a number of examples, we discover that there are two ways in which the algorithm can terminate. One way for termination is where n is eventually reduced to 1. This can happen when the largest prime factor is present more than once (eg., as in the case of 18 where the factors are 2 * 3 * 3). The other possible situation is where we terminate with a prime factor that only occurs once (eg., the factors of 70 are 2 * 5 * 7). In this instance we have a termination condition where n > 1. Therefore, after our loop terminates we must check which termination condition applies and adjust the prime factors accordingly.

The only other considerations are the initialization conditions and the dynamic generation of primes as required. Since we have already considered the prime number generation problem before, we will assume there is a function available which when given a particular prime as an argument returns the next prime.

Reference


How to Solve It by Computer (Prentice-Hall International Series in Computer Science) by R. G. Dromey.


Related Articles

tdd