# [Community Puzzle] Divide the factorial

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 don’t know what else to do…

Thanks

Do you find more or less?

I have no info about why my code doesn’t work… That’s the problem

Is there a way to have feedback from the validation tests ?

Maybe your solution is too slow.

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!

Eeek.
Oook. I use an other strategy :

• i decompose a in prime factors (with exponents)
• then i parse b! to to get the lowest common one

by reading you, i guess my solution is too slow…

question about your solution, why does the limit of max(a, b) isn’t enough ? (you can’t have a prime > a,b that divides a or b, am i wrong ?)

Hello,

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?

1 Like

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.

Finally done ! 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!.

Thanks a lot for helping 1 Like

Nice.
Although I’m still curious to know about the values of A and B for the last validation test… Are they above 10^7?

They should not.

@nicolas_patrois Can you add the corner case I described above?

## Validator 4…

3000000 < A < 3500000
7000000 < B < 7500000

• danBhentschel

It’s not my puzzle and I’m not level 30 or more.
I’m sorry, I can’t do that. My current solution passes all validators but is wrong. For case 9 10 it should have returned 2 but it returns 4 instead.

Please add test cases and validators where divisor is a square of prime number and also where the divisor is e.g.355 = 75.

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”

I really enjoyed this puzzle !

1 Like

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.