I'm taking a breather from some of the more general algorithms to tackle some of the more narrowly-defined algorithms. Today I looked at a couple algorithms relating to prime numbers.
I coded up a program to get the prime factors of a number--this took some time, but was perhaps the easiest part of my project thus far. It's pretty clear when this algorithm needs to be used, and there aren't any alterations that need to be made based on the problem (at least that I can think of).
Perhaps most interestingly, I discovered that this algorithm, combined with backtracking, can be used to solve the more common problem of finding all the factors of a number. In fact, one of the particular solutions I worked with in backtracking, generating subsets, is exactly the idea applied here. Basically, the prime factoring algorithm produces the primes, and then the subset algorithm generates all possible subsets of those prime factors. The product of the elements in each subset is a factor.
No comments:
Post a Comment