Menu
Possible Duplicate:
A number as it’s prime number parts
I have this homework assignment of mine, hard as hell, where I have to get all the distinct prime partitions of a given number. For example, number 7 has five different prime partitions (or five different ways of representing the 2 prime partitions it has):
As you can see, the number itself is excluded in the case it's a prime. I don't have to print all the distinct partitions, only the number of them.
So I'm a bit lost with this. I've been completely unable to produce any code, but I think I should approach this from a dynamic programming kind of view. I'm only asking for some hints. Has anyone got an idea? Thanks in advance.
The highest inputted number is 100. Also, the running time of the program cannot exceed 1 second, and the memory limit is 128 MB.
516
The distinct primes of a number are the different prime numbers that occur in the factorization of that number. For example, the prime factorization of 20 is 2 × 2 × 5. Here the distinct prime factors of 20 are 2 and 5.
Students sometimes believe that all prime numbers are odd. If one works from “patterns” alone, this is an easy slip to make, as 2 is the only exception, the only even prime. One proof: Because 2 is a divisor of every even number, every even number larger than 2 has at least three distinct positive divisors.
The L.C.M of any two distinct prime numbers is their product.
A sphenic number is a product pqr where p, q, and r are three distinct prime numbers. In other words, the sphenic numbers are the square-free 3-almost primes.
To solve this one you are going to need to combine three ideas:
Say the given number is n:
find all primes less than n, as shown here.
dynamically calculate the subset sum from your prime array and n. A few hints are here and here
then, calculate the number of distinct permutations of each answer you get from step two, as here.
Now of course, this is just a hint. But it should help you a great deal to cook up your final code.
126
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
