Decomposition of number into prime numbers

Question

I'm trying to create a pascal program for decomposition of prime numbers, i.e.

16 = 2*2*2*2
210 = 2*3*5*7

I should input a number and I should return the prime numbers decomposition. I don't understand the solution in mathematical sense, could someone explain me this algorithm or pseudo code, as long as I understand what I'm creating programming isn't really an issue.

Thanks

Answer 1

A naive way of doing this is to:

k = 2
N = 210
while N > 1:
    if N % k == 0:   // if k evenly divides into N
        print k      // this is a factor
        N = N / k    // divide N by k so that we have the rest of the number left.
    else:
        k = k + 1

The main premise, is that FACTOR(N) is equal to k * FACTOR(N / k), if k divides N. So keep doing this over and over until you can no longer factor N. This way, you get k1 * k2 * k3 * FACTOR(N / k1 / k2 / k3) etc.

If you start with small numbers and work up, you'll only pull out the prime factors.

So, for 210, you get:

k = 2
N = 210

k divides N, so print 2, N becomes 105
k no longer divides N, so k becomes 3
k divides N, so print 3, N becomes 35
k no longer divides N, so k becomes 4
k does not divide N, so k becomes 5
k divides N, so print 5, N becomes 7
k no longer divide N, so k becomes 6
k does not divide N, so k becomes 7
k divides N, so print 7, N becomes 1
N is now equal to 1, so stop.

You get 2 3 5 7 

A basic improvement would be that you only have to iterate through the primes. So, you could have skipped over 4 and 6 in the above example.

Answer 2

A prime number is an integer with exactly two divisors. For example, 13 is prime, since it is divisible only by 1 and by 13 (two divisors). 14 is not prime, since it is divisible by 1, 2, 7 and 14 (four divisors). 4 is not prime, since it is divisible by 1, 2 and 4 (three divisors). By convention, 1 is not a prime number, but that's not really important here.

Every integer larger than 1 has a unique factorization (decomposition) into prime numbers. In other words, there is only one (multi)set of prime numbers such that their product is equal to the given number. For example:

14 = 2 * 7
16 = 2 * 2 * 2 * 2
4 = 2 * 2
13 = 13

Your task is to write an algorithm that takes on input an integer larger than 1 and outputs a list of prime numbers such that their product is equal to the input number.

Arguably the easiest algorithm for factorization is trial division.