2

As part of my effort to explore algorithms through project Euler, I'm trying to write a method that will accept an integer 'n', number of factors 'k' and factorize it. If its not possible, it will throw an error.

For instance, if I enter factorize(13257440,3), the function will return a list of all possible unique sets with 3 elements where the product of the 3 elements is equal to 13257440.

My first though is to generate a multi-set of prime factors of n (with 'm' representing the size of the set), then partition the set into k partitions. Once partition sizes are determined, I would treat it as a combinations problem.

I'm having trouble however formulating algorithms for the two parts above, and have no idea where to start. Am I over complicating a simple problem with a simple solution? If not, what are some recommended approaches? Thanks!

Ellyl
  • 61
  • 4

1 Answers1

0

  1. primes decomposition

    find all primes that can divide n without remainder. Use sieve of Eratosthenes to speed up the process considerably.

    You can use/modify mine (warning this link is project Euler spoiler)

    now you need to modify the code so the prime list will change to multiplicants list. For example if n=12 this will found { 2,3 } and you need { 2,2,3 } so if divider prime found check it again and again until it is not divisible anymore each time lessen the n.

    Add a flag to each found prime (is used?) to speed up the next step...

  2. The combination part

    I assume the multiplicants can be the same so add k times 1 to the primes list at start and create function that create all possibilities of numbers up to some x from found unused primes. Add the counter for unused primes m so at start the m is set to prime list size and the flags are all set to unused.

    Now you need to find all possibilities of using 1..m-k+1 numbers from the list. Each iteration set the picked number as used and decrease m so it is something like:

    for (o=1;o<=m-k+1;o++)

    here find all combination of o unused numbers so handle it as o digit number generation with base o without digit repetitions it is o! permutations.

    You can use this (warning this link is Euler spoiler):

    do not forget to set flag for each used number and unset it after iteration is done. Rewrite this function so it is iterative with calls findfirst(), findnext() similar to mine permutation class.

    Now you can nest all this k times (with use of nested fors from the permutation link or via recursion each time lessen the k and n)

Spektre
  • 49,595
  • 11
  • 110
  • 380
  • I'm not understanding the combinations part. Are you saying to find all possible combinations of the available primes 'm-k+1' times, each time removing an element from the available set? How does that lead to all possible k factors? – Ellyl May 31 '15 at 03:40
  • @Ellyl it is just an intermediate step it will create all numbers that can be constructed from the found primes (you should ignore duplicates) so you will have k-1 such steps nested together and the last factor is what is left unused or `n/all found multiplicants` for current iteration. The point is to use only yet unused numbers to avoid many duplicates ... – Spektre May 31 '15 at 15:35