Hi, i’m stuck with the validation test 4 of this problem. (It’s a Community Puzzle)

My code validates all the test cases except this one (and not with an hardcoded solution ^^)
I think the complexity of my solution is good (using prime factors and freq…)
I identify the special case “a = 1” (with answers like 0, Integer.MAX_VALUE, Double.POSITIVE_INFINITY, etc.)

I had the same issue yesterday, the Validation Test 4 wouldn’t pass.
But everything else would, and the algorithm looked definitely correct.

As you said, one possible way to solve this puzzle is by looking at the prime factors.
You probably have some kind of sieve function that generates prime numbers under a certain limit?

Well, I have such a function and what it does is compute the list of prime numbers below limit. This function allocates a big array of size limit to do the lookup.

In the beginning I chose limit to be max(a, b) + 1 to only generate the prime numbers that are necessary. This passed all the validation tests except the last one.
But by using limit = 10 ^ 7 + 1 instead, the last test would just pass!

However, trying with limit = 10 ^ 8 gives a MemoryError directly in the IDE (using Python).

So my guess is that the input used for the last test case doesn’t respect the constraints mentioned in the problem statement (1 ≤ A, B ≤ 10^7), meaning either A or B is above 10^7.
Or just a general memory error, depending on how many objects you allocate (you seem the be using Java).
Probably something worth checking!

As long as you have a good prime factorization algorithm, a solution for this puzzle can easily handle a = 10^30.

But this problems lacks of edge test cases when you need to take multiplicity of a prime factor into account.

Let’s a = 24 = 2 ^ 3 * 3 and b = 1000.
There are some solutions that returns 498, which is the multiplicity of 3 in 1000!, whereas the correct answer is 331, the multiplicity of 2.

Can someone edit this kata to add a test and a validator with this corner case?

It is indeed enough.
In my case, I implemented a simple version of the sieve of Eratosthenes, which allocates an array of booleans to keep track of the prime numbers. For example: if B = 12345678, it will allocate an array of 12345678 booleans.
And creating such a big array makes the program crash with a memory error.

But at the same time, creating a fixed-size array of 10^7 booleans works and fits the memory limit.

The part about parsing B! with the prime factors of A was too slow. I improve the efficiency using Eratosthenes’ way of incrementing with the prime factors of A to parse B!.

What I love about this puzzle is that my first reaction was similar to the above (Prime numbers, sieve, fancy number theory), but after some thought and looking into the essence of the problem - a beautiful and simple solution exist that doesn’t require any big arrays or complex calculations.

All it requires is looking at the core of the question here, and remembering the basic rules of “power of n”

Still no correction after two weeks.
Two edge cases identified by MMMAAANNN and me.
This puzzle became a puzzle of the week and still no answer coming from the staff, that’s pretty awful.
Noone read the forum?