May contest already ended, but I could not view any solution. The server keep saying:
What happened?
May contest already ended, but I could not view any solution. The server keep saying:
What happened?
Same here, probably there are some background tasks to do. Also countdown for Cook-off is not displayed on main page.
@betlista: I’m really pissed off about this problem since I’ve been thinking over it for 5 days and all my final exams are next week. I know the pattern relates to Prime, but I don’t know how to make it faster. Any idea?
In Java you can use BigInteger.isProbablePrime(50)
here is link to my solution - http://ideone.com/wxM1jt
@betlista: Thanks a lot. My algorithm for finding previous prime is the same as yours, whereas my algorithm for checking prime is Miller Rabin but I got TLE many times which made me suspect whether my idea is correct. I really want to see a C++ solution now.
How I reached the answer :
Wikipedia explanation:
First 500 values of totient Function : Got clear we have to print prime before n
Maximum gap between Prime numbers doesnt exceed 1476
To check a number is prime or not :
Fermat’s primality test
Miller-Rabin primality test
Well Written Miller-Rabin Primality Test Algorithm
Nice explanations of Miller Rabin test
Other test may include Sieve of Eratostheness, Sieve of Atkin, AKS primality test
Some Similar Problems
I think this information might help you, and dont ruin your exams now, just hold your curiosity for some days… hope you will get the better of this… (y)
In addition: even with 20 iterations python code gets AC, while C++ gets TLE with more number of iterations.
I’m afraid that
Maximum gap between Prime numbers doesnt exceed 1000
simple doesn’t hold, see the table - http://en.wikipedia.org/wiki/Prime_gap#Numerical_results as I understood it is up to 1400 for n <= 10^18, but that’s just a detail…
my c++ solution with 7 iteration got accepted
lucky you!
As of August 2009 the largest known maximal gap has length 1476, found by Tomás Oliveira e Silva. It is the 75th maximal gap, and it occurs after the prime 1425172824437699411
Can you please check the links. They should work now.
opps… my bad…, have wrote it without confirming… sorry… my bad…
Nope, ain’t working.
Same here - not working still…
not working
However, the contest page says,
The May Contest has ended!
The editorials for May Challenge will be uploaded tomorrow.
All problems will be added to the practice section.
Solutions are public for all problems.
Winners Blog Post will be updated soon. The ratings have been calculated.