https://www.codingame.com/training/medium/regular-polygons
Send your feedback or ask for help here!
Created by @Witman,validated by @nicola1,@Master_Zain and @Razovsky.
If you have any issues, feel free to ping them.
Nice puzzle, when b gets big, I get a time exceeded msg. No idea how to optimize !
We can think about eliminate power 2 elements using this form of div 2:
j>>=(int)(log2(j & -j));
as this will avoid one loop, it will help to resolve medium range test but not the last test.
try to make a library of distinct products of fermat prime numbers and then use it to count its multiply in provided range. (think out of the box)
vector dist_Fermat_primes={1, 3, 5, 15, 17, 51, 85, 255, 257, 771, 1285, 3855, 4369, 13107, 21845, 65535, 65537, 196611, 327685, 983055, 1114129, 3342387, 5570645, 16711935, 16843009, 50529027, 84215045, 252645135, 286331153, 858993459, 1431655765};
The powers of 2 are solutions to the problem, so I already did that. It’s the last test that I can not pass !!
I already did that. I think the problem is in the way i loop over each number between a and b !!
After 3 days of thinking about the problem, I finally got all the tests working…
My initial mistake was that although I read up about Fermat Primes (and that there are only 5 of them) I had the feeling that hard-coding them in my solution is somehow cheating 
So I tried checking numbers to see if they are Fermat primes. And although I did everything to avoid checking the same number twice it was still pretty slow.
Hardcoding the 5 Fermat primes in a Set and checking for every number between a and b whether it is divisible only by those 5 numbers and 2, got me through the medium test, but it was still awfully slow for the long range.
And as you suggest, the problem is looping through everything in between a and b. So my last version (and this one passes all the tests), constructs all the possible 31 product of Fermat primes and saves them in a Set (plus the number 1) and then I just go over each of them and keep them multiplying by 2 as long as the product is less than b. So instead of checking numbers, I actually just generate the correct ones.
2 Likes
Yes, that is what I mean, instead of checking, create all multiplies of fermat primes in provided range and then just count what was created, congratulation THaruca.
Now I see what you meant omarekik. That worked, thank you 
But what if the last condition b<2^31 was to change? Can we calculate the product of Fermat’s primes dynamically? hmmm
I pass test 1,2 ,3 and 4, but not the last test.
I find 483 instead of 494.
Anybody who can help?
Hi, there is something i don’t understand.
The statement says :
A Fermat prime is a prime number of the form 2^(2^m)+1 . Where m is a natural number.
So imo the fermat primes are :
3 (m=0)
5 (m=1)
17 (m=2)
257 (m=3)
65537 (m=4)
4294967297 (m=5) but it is not a prime number.
And in the first test, we can see that 4 is the product of a power of 2 and a fermat prime.
Did I miss something ?
The description does not say all numbers of the form 2^(2^m)+1 are Fermat primes. My interpretation of what it wants to say is that if a number is prime and in the form 2^(2^m)+1, then it is a Fermat prime.
Does this make sense or answer your question?
1 Like
My problem is : we have to found numbers which are product of a power of two and a Fermat prime.
“4” seems to be one of those numbers, I don’t understand why.
The puzzle statement says:
the product of a power of 2 and any number of distinct Fermat primes (including none).
1 Like
Ok so it is a product of a power of two and a Fermat prime OR just a power of two ?
Thank you, I misunderstood that.
There is something else i misunderstood (thank you google translate !) : “any”.
I understood “anyone of them” but with google it seems to mean “one or several”.
Hi,
I’m puzzled 
I have a code fast enough to get all the IDE tests and pass the two first tests.
But for any reason, the results are quie largely underestimated by this code…
If someone could have a look on my code to evalute the miss I have certainly in the puzzle understanding it would be great.
Just ping in MP I’ll send it, it is quite short and logs are quite explicite.
Thanks !
I can try your code, just tell me its language.