Expert: Josh - 12/1/2010

Question
what is the prime factorization of 490? in "tree form". thanks.

Answer
Hi Joseph,

The theory states that all positive integers may be written as a product of prime numbers.

The way we go about finding the prime factorization of a number X is as follows:

BOTTOM-UP METHOD
================
First, write down a sizable list of prime numbers. [Remember: by definition, a prime number cannot be divided by anything else other than the number itself and 1]
P = {2,3,5,7,11,13,17,19,23,...}

Second, starting with the smallest prime number in P, try successively dividing the number X until it divides no more. When one prime does not divide X, we move onto the next higher prime number. This continues (at most) until we reach a prime number larger than the square root of X.

This is best illustrated with an example.

Let X=490.
Pick the smallest prime number from the list P. We begin with "2".
Since 2 divides 490, in particular, 490/2=245, we have identified the first prime factor "2". At this point, we set X=245.

Again, we ask, does 2 still divide 245? The answer is no. So, we move on to the next larger prime number in the list P. We pick the prime number "3". Now, since 245/3 has a remainder of 2 (and not zero), we conclude that 3 does NOT divide 245. So, we select the next prime number from the list P. We pick the prime number "5". This time, 245/5=49 (5 divides 245 perfectly). So, "5" is a factor of 490. At this point, we set X=49.

We can keep going, until the number X becomes irreducible. Here, we find 49=7*7. So, we have reached the end.

Retracing our steps, we find that
490 = 2 x 245
   = 2 x 5 x 49
   = 2 x 5 x 7 x 7.

TOP-DOWN METHOD
===============
The prime factorization tree-approach is what we call a top-down method. The first step (and each subsequent stage) requires us to break a number into the product of two numbers. For a relatively small number like 490, it is easy to spot that it equals 49 x 10. So, away we go. The procedure may be called recursively to break each node in the tree into two branches. The difficulty arises when we are given a large number like 69684615. It is not immediately obvious how it should be broken up into two parts (with similar size) to keep the tree looking balanced.

[Note: To ensure everything aligns, copy and past the following diagram into a text editor and use a font such as "Courier" where each character has equal spacing]

...........490
........./.....\
........49.....10
......./..\.../..\
......7...7...2...5

Here is another example for the number 240:
...........240
........./.....\
........24.....10
......./..\.../..\
......3...8...2...5
........./.\
........2...4
.........../.\
..........2...2
So, 240 = 2 x 2 x 2 x 2 x 3 x 5