Geek Answers Handbook

Number of different simple sections

Possible duplicate:
A number as its prime numbers

I have my homework as hell, where I have to get all the individual primary sections of a given number. For example, number 7 has five different simple sections (or five different ways of representing the two main sections):

  • 5 + 2
  • 2 + 5
  • 3 + 2 + 2
  • 2 + 3 + 2
  • 2 + 2 + 3

As you can see, the number itself is excluded if it is simple. I do not need to print all the individual sections, only their number.

So I lost this a bit. I was completely unable to create any code, but I think I should approach this in terms of dynamic programming. I just ask for some hints. Does anyone have an idea? Thanks in advance.

The highest number entered is 100. In addition, the program’s runtime cannot exceed 1 second, and the memory limit is 128 MB.

+4
source share
4 answers

To solve this problem, you will need to combine three ideas:

Say the indicated number n:

  • find all primes less than n as shown here .

  • dynamically calculates the sum of the subset from your simple array and n. Some tips here and here.

  • then calculate the number of different permutations of each answer obtained from step two, as the quality here .

Now, of course, this is just a hint. But that should help you a lot to prepare your final code.

+2
source

You cannot improve brute force here, unfortunately, too much. The only thing you need to do is use the Eratosthenes sieve to pre-calculate all primes to a given number. After that, given the number N, recursively print all its sections, where the smallest prime is each prime from the list of primes in sequence (remember that it is the smallest so that you don't repeat the sections).

EDIT: Having learned that you need to know the number of sections: The best solution would be to use dynamic programming. Again, you will need to memoize in an array with two dimensions mem[MAX_SIZE][MAX_SIZE] first index is the number that you calculate for the solution, and the second index is the minimum prime number that you should use for the section.

+1
source

So, in the form of hints as opposed to the answer:

  • As mentioned elsewhere, you can precompute primes.
  • Can you reuse results from a smaller number? So, if you know the actual permutations for 5, does this help find any of the actual permutations for 7?
  • Is there any structure for the results, and if so, can you use this structure to avoid repeating the calculations? For example, you list 5 permutations for number 7, but they have some similarities with each other - is this a general trend and what is it?
  • Assuming you find an internal structure and can use smaller results to help find larger ones, can you do both - can you completely avoid storing intermediate results?
  • Finally, do I need to list each ordered combination or just return the number of ordered combinations? You can save the calculations here.
+1
source

You can see the math sections on Wikipedia , in particular the sections on Generating Functions and Generations with a limited division of Functions halfway down the page. He mentions the generating function for partitions consisting of partial terms (given by the set T of natural numbers).

Let the number of non-charged simple sections of n be equal to R (n). You can get R (n) from the generating function by taking the nth partial derivative wrt x and then setting x = 0. This can be difficult.

One caveat: these sections are order independent (that is, 1 + 2 and 2 + 1 are only counted as one section).

+1
source

More articles:


All Articles