-1

How do I calculate a number if its number of factors (N) and number of prime factors (K) are given?

Example: if N = 4 and K = 2 is given then the only possible value will be 6

Explanation : of the above is 6 has 4 factors (1,2,3,6) of which 2 are primes (2,3). So the only possible value is 6.

Mitchell van Zuylen
  • 3,905
  • 4
  • 27
  • 64
Alex Ed
  • 41
  • 2
  • 9
  • 1
    Notice that for N = 4 and K = 2 you could also get 10 -> 1, 2, 5, 10. Do you need uniqueness or just find a valid number? – mgostIH Apr 06 '20 at 08:37
  • Welcome to Stack Overflow.I suggest you to kindly try to code for the above problem and whenever you face a problem post your **code** along with the problem you face. Read this [link](https://stackoverflow.com/help/how-to-ask) to get an idea on how to post question. – Mohamed Shabeer kp Apr 06 '20 at 08:39
  • 1
    there can be many such numbers potentially, including none. – Will Ness Apr 06 '20 at 08:59
  • @MohammedShabeerkp i want to code this problem but unable to get the approach. – Alex Ed Apr 06 '20 at 09:04
  • `numfactors(num) = PRODUCT { (1+i) FOR (p,i) IN prime_factorization(num) }` where e.g. `prime_factorization(18) = { (2,1) , (3,2) }` because `18 == 2^1 * 3^2`. start from here. understand why that formula is true, and you'll be able to solve it. ---- a [similar question](https://stackoverflow.com/q/61026482/849891) was also recently asked. – Will Ness Apr 06 '20 at 09:04
  • @mgostIH you are right, its okay if there is no such number for a given pair but what if there exist such number then how to find it. – Alex Ed Apr 06 '20 at 09:06
  • 2
    I'm voting to close this question as off-topic because it is not about programming. – High Performance Mark Apr 06 '20 at 09:54
  • @HighPerformanceMark its about programming – Alex Ed Apr 06 '20 at 10:11
  • @MohammedShabeerkp please take a look at the code – Alex Ed Apr 06 '20 at 10:12
  • @WillNess , i have added the code please take a look at this – Alex Ed Apr 06 '20 at 10:13
  • 1
    I suspect OP is trying to solve [this problem](https://stackoverflow.com/questions/61054171/time-limit-excedeed-error-for-large-values/61057036#61057036) and asked the wrong question here (how to find a number with N factors and K prime factors) when the question they are actually trying to solve is whether such a number exists, not to produce such a number (although producing one, if any exist, is fairly simple). – Eric Postpischil Apr 06 '20 at 10:14
  • @Eric Postpischil There are at least three similar questions in the last day - perhaps online contest. – MBo Apr 06 '20 at 14:36

1 Answers1

2

Any integer number can be represented as product of powers of primes:

I = 2^p1 * 3^p2 * 5^p3 * 7^p4 * 11^p5 * ....

Total number of all its factors is

N = (p1+1) * (p2+1) * (p3+1) * ....
     \__________________________/ 
            K multipliers

So you you need to represent the value N as a product of K factors larger than 1.

Factorize N into primes, group these primes into K groups.

Imagine you have N=420 with 5 prime factors: 2 2 3 5 7 and K=3. Make groups 2*2, 3*5, 7 (or any other combination) so corresponding powers to make I are 3,14,6

For example, having N = 12 and K=3, you can represent 12 = 2 * 2 * 3 and use a product of any two primes with a square of a third prime as the number I. The smallest such value is 60 (2^2 * 3 * 5), the next one is 90 (2 * 3^2 * 5) and so on (for example, 3 * 7 * 11^2 is also a solution).

For the case N = 12 and K=2 you can represent 12 = 3 * 4 and get results as p^2*q^3 or 12 = 2 * 6 and get results as p*q^5 where p,q are distinct primes

For the case N = 12 and K=4 you cannot represent 12 as product of four integers larger than 1, so it is impossible to produce result with these arguments

MBo
  • 77,366
  • 5
  • 53
  • 86