Geek Answers Handbook

Number in which this number

I need to print the number of ways you can represent a given number as parts of a prime number.

Let me explain: let's say they gave me this number 7. Now, first of all, I need to find all primes that are less than 7, which are 2, 3, and 5. Now, how much way can I sum these numbers (I can use one number as many times as I want) so that the result is 7? For example, number 7 has five ways:

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

I completely lost this task. At first, I decided that I was creating an array of elements used: {2, 2, 2, 3, 3, 5} (7/2 = 3, so 2 should appear three times. The same thing happens with 3, which turns out to be two occurrences). After that, scroll through the array and select the “leader”, which determines how far we are in the array. I know the explanation is terrible, so here is the code:

 #include <iostream> #include <vector> int primes_all[25] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}; int main() { int number; std::cin >> number; std::vector<int> primes_used; for(int i = 0; i < 25; i++) { if(primes_all[i] < number && number-primes_all[i] > 1) { for(int k = 0; k < number/primes_all[i]; k++) primes_used.push_back(primes_all[i]); } else break; } int result = 0; for(size_t i = 0; i < primes_used.size(); i++) { int j = primes_used.size()-1; int new_num = number - primes_used[i]; while(new_num > 1 && j > -1) { if(j > -1) while(primes_used[j] > new_num && j > 0) j--; if(j != i && j > -1) { new_num -= primes_used[j]; std::cout << primes_used[i] << " " << primes_used[j] << " " << new_num << std::endl; } j--; } if(new_num == 0) result++; } std::cout << result << std::endl; system("pause"); return 0; }

It just doesn't work. Just because the idea behind is not so. Here are some border details:

  • Time limit: 1 second
  • Memory Limit: 128 MB

In addition, the largest number that can be given is 100. That's why I made an array of primes below 100. The result grows very quickly, as this number gets larger, and the BigInteger class will be needed later, but this is not a problem.

Several results are known:

 Input Result 7 5 20 732 80 10343662267187

SO ... Any ideas? Is this a combinatorial problem? I don't need code, just an idea. I'm still new to C ++, but I will get along

Keep in mind that 3 + 2 + 2 is different from 2 + 3 + 2. In addition, if this number were prime, it is not taken into account. For example, if the given number is 7, only these amounts are valid:

 2 + 2 + 3 2 + 3 + 2 2 + 5 3 + 2 + 2 5 + 2 7 <= excluded
+4
source share
3 answers

Dynamic programming is your friend here.

Consider the number 27.

If 7 has 5 results, and 20 has 732 results, then you know that 27 has at least (732 * 5) results. You can use two system variables (1 + 26, 2 + 25 ... etc.) Using pre-calculated values ​​for the ones you go. You do not need to count 25 or 26 because you have already made them.

+9
source

The concept you are looking for is the "simple sections" of a number. S-division of numbers - a way to add numbers to achieve a goal; for example, 1 + 1 + 2 + 3 is section 7. If all additions are simple, then the partition is a simple section.

I think your example is wrong. As a rule, the number 7 has 3 simple partitions: 2 + 2 + 3, 2 + 5 and 7. The order of the terms does not matter. In number theory, the function that counts the primary partitions is kappa, so we say kappa (7) = 3.

The usual kappa calculation is done in two parts. The first part is a function for calculating the sum of simple factors of a number; for example, 42 = 2 · 3 · 7, therefore sopf (42) = 12. Note that sopf (12) = 5, because the sum has only individual number coefficients, therefore, although 12 = 2 · 2 · 3, when calculating The amount included is only 2.

Given sopf, there is a long formula for calculating kappa; I will give it in LaTeX form since I don’t know how to enter it here: \ kappa (n) = \ frac {1} {n} \ left (\ mathrm {sopf} (n) + \ sum_ {j = 1 } ^ {n-1} \ mathrm {sopf} (j) \ cdot \ kappa (nj) \ right).

If you really need a list of sections, not just an account, there is a dynamic programming solution that @corsiKa pointed out.

Discuss in more detail the main sections of my blog , including the source code for creating both an account and a list.

+3
source

Here's an efficient implementation that uses dynamic programming, such as corsiKa, offers, but does not use the algorithm that it describes.

Simple: if n accessible through k different paths (including one-step if it exists), and p is simple, then we build the paths k to n+p by adding p to all paths to n . Given all of these n < N , you get an exhaustive list of valid paths to n . Therefore, we simply summarize the number of paths detected.

 #include <iostream> int primes_all[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}; const int N_max = 85; typedef long long ways; ways ways_to_reach_N[N_max + 1] = { 1 }; int main() { // find all paths for( int i = 0; i <= N_max; ++i ) { ways ways_to_reach_i = ways_to_reach_N[i]; if (ways_to_reach_i) { for( int* p = primes_all; *p <= N_max - i && p < (&primes_all)[1]; ++p ) { ways_to_reach_N[i + *p] += ways_to_reach_i; } } } // eliminate single-step paths for( int* p = primes_all; *p <= N_max && p < (&primes_all)[1]; ++p ) { --ways_to_reach_N[*p]; } // print results for( int i = 1; i <= N_max; ++i ) { ways ways_to_reach_i = ways_to_reach_N[i]; if (ways_to_reach_i) { std::cout << i << " -- " << ways_to_reach_i << std::endl; } } return 0; }

Replacing typedef ways with a large integer type is left as an exercise for the reader.

0
source

More articles:


All Articles