Prime Factorization

[Paul the Abstinence Panther]

Hey, decaying remnants of Aisenfield! Yesterday, I re-learned prime factorization and realized that I don't intuitively get it.

Basically, prime factorization is saying that any number can be represented by a product of prime numbers. In order to do this, you divide by the smallest prime number that will yield an integer result, then repeat.

60, for example.
60/ 2 = 30.
30/2  = 15
15/3  = 5.

5 is the greatest prime factor.

What I have trouble grasping, though, is how I know that simply dividing by 3 during the first step couldn't give me a bigger prime factor? Why is always dividing by the smallest option the best choice?

[CM]

Is it necessarily the best? If you keep dividing by prime factors in any order, you'll have a list of numbers among which the largest will be obvious.

Say, if we look at the number 210,
210 / 7 = 30
30 / 2 = 15
15 / 5 = 3
3 / 3 = 1

So my prime factors are 3, 7, 2, and 5. It's evident that 7 is the largest; what does the order really matter? Dividing a number n by the smallest factor each time just ensures that the last factor is the largest, because you'll have eliminated everything smaller than it. You don't know what the GPF is, and the lowest prime factor is the only number you know won't eliminate the GPF (unless n is a prime number).

[Paul the Abstinence Panther]

That was remarkably clear. I pretty much get this now. CM, you are god.