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.
Submit an article or tip