Okay folks, this should be simple, but maybe not.
The goal is to write a function that takes a positive integer and returns a list of its prime factors. So if you did 12 you should get the list [2, 2, 3]
As neither 1 nor zero are prime, as a result should return an empty list.
This is taken from a #tdd #Kata, so if you have not done this one I encourage you to do so. If you are not into #TDD then solve it however you like.
🇳🇱
@Absinthe Easy to solve yes, but rather difficult to solve efficiently!
Thats solvable (goes into NP stuff but I wont invoke this here)...
Think of it like this creating prime numbers is a much easier task than checking if a number is prime. Its the whole reason cryptography works, we can generate large primes for our keys but getting those primes out after the fact is computationally difficult.
So a TDD would be a simple matter of generating a set of primes (easy) then multiply them together to get the value under test. Then send that value off to be tested and verify if the results agree with the original list of primes you generated.
Reversing the process makes all the difference in the world when testing stuff like this.
Checking for primality is not that hard either, the factorization is hard and is the reason cryptography works (certain schemes).
That said, even if it's an easier task computationally, it's not necessarily easier to implement, especially efficiently, especially for large numbers.
Sure, skip the primality test, if your genrerator does not rely on it, but who's going to test the generator?
Maybe a trivial primality test that does not need a test itself? (oh no already violating TDD) Use it to test the generator, which you can then use to test a more sophisticated primality test that you can then use to test the generator for even bigger numbers? This is a very trollish kata for TDD, and an example of a problem where you're better off relying on theory to prove correctness, an maybe only testing some components not the problem/solution as a whole.
@namark
Yea sorry I misspoke, I should have said factorization. Sieves would make it easy to chec if something is prime.
@Absinthe