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. 
Thanks for the answers
I use an other strategy :
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?
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 
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?
They are not. To answer your question:
3000000 < A < 3500000
7000000 < B < 7500000
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 !
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?
Can you provide a list of test cases that you think that should be added? 2 new test cases have been added.
Hi,
Try 48 16. The result should be 3.
The problem is that most people just use the biggest prime but that’s not necesarily the biggest divisor…