Snack Break #2 help?
I think I am on the right track but I dont know how to get prime numbers of x. I don't even know if I am doing what I am supposed to be doing.
I'm not really looking for a direct answer, as in giving me the code that I should use, but trying to lean me in the direction I should be going.
This is the question:
01 | --[[ |
02 | so it makes a table based on what x is |
03 |
04 | bosswalrus [11:01 PM] |
05 | and the things in the table should multiply up to x |
06 |
07 | bosswalrus [11:01 PM] |
08 | but should be prime numbers? |
09 | --]] |
10 |
11 | function primeFactorization(x) |
12 | output[#output + 1] = x |
13 | end |
14 |
15 | local output = { } |
1 answer
Do you know what a prime factorization is?
Example: 90 has a prime factorization of 2 * 3 * 3 * 5.
There are a few ways to go about implementing this in Lua, but first think about how you'd do it yourself.
There are two main ways to approach this.
By Hand
Let's take 1650. How do we factorize it? Well, we can pick some numbers that divide it. Pretty clearly it's divisible by 10, so
1650 = 10 * 165.
We can then split each of these into prime factors. 10 is just 2 * 5, and 165 is clearly divisible by 5, so 165 = 5 * (165/5) = 5 * 33:
1650 = 10 * 165 = (2 * 5) * (5 * 33).
Finally, 33 is just 3 * 11. We end up with all prime numbers then. So
1650 = 2 * 5 * 5 * 3 * 11.
Describe what we did more exactly:
- To get the factors of
n,- Pick a factor of
n, call itf. - Get the factors of
fand the factors ofn / f. - put them together.
- Pick a factor of
The big question left is, how do you "pick a factor of n"?
A factor divides n cleanly, meaning there is no remainder after division. You'll probably need n % f == 0 as the condition when searching for an appropriate f. Remember to forget about f=1, since 1 is not prime!
Fundamental Theorem of Arithmetic
All integers have a unique factorization. In particular, that means that for any n,
1 | n = 2^a * 3^b * 5^c * 7^d * ... |
where 2, 3, 5, 7, ... are the primes and a b c ... are non-negative integers.
Thus you can just figure out how many times 2 goes into n, how many times 3 goes into n, etc.
This approach requires
* a list of prime numbers
* determining if p^k divides n
Hopefully this explanation gives the information you need. There are more or less 3 ways to tackle the problem of factoring numbers -- so you should be able to pick a method that looks like it works and arrive at a solution.
0