14,937,843 members
5.00/5 (1 vote)
See more: (untagged)
Good Day,

It's me again. This question is one of the questions in ACM ICPC 2006 - Philippines.

Basically, you need to express a large number as a product of its Primes.

For example:
120 = 2x2x2x3x5 (or 2^3x3^1x5^1)

I'm lost on how to begin to tackle this problem. Please advice.

Thank you.

Posted

## Solution 1

Ian Uy wrote:
I'm lost on how to begin to tackle this problem. Please advice.

As a college student, you really should be able to do this. It's basic math.

What you will want to search for is called "prime factorization." The easiest-to-understand technique is called "trial division."

On paper, you start by writing down your large number (let's call it 'n'). Then try to think of another number which divides evenly into n without any remainder. That number is a factor of n. It's easiest to start with small numbers.

In your example, what number divides evenly into `120`? How about `2`? Yes, `120/2=60`. So write down `2` and `60` (those are factors of `120`, but not necessarily prime).

Then try to factor each number you wrote down (the `2` and the `60`). Are there any numbers (other than 1) that divide into `2` evenly? No, so `2` is a "prime factor" of `120` (i.e. `2` cannot be divided any further).

How about the `60`? `60/2=30`. So, there is another `2` that is a prime factor of `120`. So far we have the factors of `120=2,2,30`. Now factor the `30` and keep going.

Keep going until you run out of numbers that can be divided evenly. Those will be your prime factors.

120 factored = 2,60 (2 is prime)
60 factored = 2,30 (2 is prime)
30 factored = 2,15 (2 is prime)
15 factored = 3,5 (both 3 and 5 are prime)
Done.

The prime factors of `120` are (from the parentheses above) `2,2,2,3,5`.

Now try writing that in code and see what you come up with. You can use this Table of Prime Factors[^] to check your answers.

## Solution 2

You do not need to divide by all numbers, only by primes. If the number is evenly divided by a prime, then keep dividing by that prime until the result leaves a remainder, then go to the next prime. There exists (google primes) a site on which there is a list of the primes for the first million numbers, the second million numbers ... to the first 15 million numbers.

Dave Augustine.

Top Experts
Last 24hrsThis month
 OriginalGriff 375 Maciej Los 265 Richard Deeming 140 Richard MacCutchan 105 Greg Utas 68
 OriginalGriff 5,310 Richard MacCutchan 2,625 Richard Deeming 2,085 Patrice T 1,320 CPallini 1,240

CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900