×

# Can't view solution after contest ended

 4 1 May contest already ended, but I could not view any solution. The server keep saying: What happened? asked 13 May '13, 16:05 2★tyrant 1.2k●20●27●34 accept rate: 12% 1 Same here, probably there are some background tasks to do. Also countdown for Cook-off is not displayed on main page. (13 May '13, 16:09) @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? (13 May '13, 16:12) tyrant2★ 1 In Java you can use BigInteger.isProbablePrime(50) here is link to my solution - http://ideone.com/wxM1jt (13 May '13, 16:13) @tyrant >> In lang other than Java you can use probabilistic methods. (13 May '13, 16:15) @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. (13 May '13, 16:23) tyrant2★ @tyrant >> for how many iterations were you running your Miller Rabin test? (13 May '13, 16:25) @betlista: I passed even with isProbablePrime(10) (13 May '13, 16:42) showing 5 of 7 show all

 4 How I reached the answer : Wikipedia explanation: Wikipedia explanation First 500 values of totient Function : Got clear we have to print prime before n First 500 values of Totient Function Maximum gap between Prime numbers doesnt exceed 1476 Prime Gap To check a number is prime or not : Fermat's primality test Fermat's Primality Test Miller-Rabin primality test Miller-Rabin primality test Well Written Miller-Rabin Primality Test Algorithm Miller-Rabin Primality Test Algorithm Nice explanations of Miller Rabin test Explanation 1 Explanation 2 Explanation 3 Other test may include Sieve of Eratostheness, Sieve of Atkin, AKS primality test Seive Of Eratostheness Seive 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) ;) answered 13 May '13, 16:28 2.7k●11●19●27 accept rate: 13% 1 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... (13 May '13, 16:36) 1 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 (13 May '13, 16:39) opps.... my bad..., have wrote it without confirming.... sorry.... my bad.... (13 May '13, 16:42)
 1 In addition: even with 20 iterations python code gets AC, while C++ gets TLE with more number of iterations. SO duscussion My solutions: Python, C++ answered 13 May '13, 16:33 8.7k●19●48●98 accept rate: 9% 1 my c++ solution with 7 iteration got accepted :P (13 May '13, 16:36) :D lucky you! (13 May '13, 16:37)
 1 From here, I found that phi(N)/N will be maximum, when the number of prime factors is minimum (which is equal to 1); and when this prime factor is maximum. This clearly means I need the largest prime less than or equal to the given N. To check whether a number is prime, I used the Miller-Rabin test, the details of which I took from here. But how many iterations? From citation number 12 in the given link, I reached here. From this, I got all my requirements. These finally led me to this Python code: def modular_pow(base, exponent, modulus): result = 1 while exponent > 0: if (exponent % 2 == 1): result = (result * base) % modulus exponent = exponent // 2 base = (base * base) % modulus return result def passesMillerRabinTest(n, a): s = 0 d = n - 1 while (d % 2 == 0): s += 1 d >>= 1 x = modular_pow(a, d, n) if (x == 1 or x == n - 1): return True for ss in xrange(s - 1): x = (x * x) % n if x == 1: return False if x == n - 1: return True return False primeList = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) def isPrime(n): for p in primeList: if n % p == 0: return n == p for p in primeList: if passesMillerRabinTest(n, p) == False: return False return True t = int(raw_input()) for tt in xrange(t): n = int(raw_input()) if n == 2: print 2 continue if n % 2 == 0: n -= 1 while (True): if isPrime(n): print n break n -= 2  And, it was AC!! answered 13 May '13, 16:50 4.2k●5●23●64 accept rate: 15%
 0 Can you please check the links. They should work now. answered 13 May '13, 16:42 454●7●10●13 accept rate: 22% Nope, ain't working. (13 May '13, 16:43) Same here - not working still... (13 May '13, 16:47) not working (13 May '13, 16:48) dvdreddy3★ 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. (13 May '13, 16:49) now fixed! (13 May '13, 16:52) We are fixing this. Some solutions are not visible. (13 May '13, 17:10) admin ♦♦0★ still can't see :( (13 May '13, 17:55) server has a bad day today, solutions were public for a while and thay are not again, admins know about this already ;-) (13 May '13, 17:57) Links for JUNONGF not working, please fix it... (13 May '13, 17:58) showing 5 of 9 show all
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,234

question asked: 13 May '13, 16:05

question was seen: 1,635 times

last updated: 13 May '13, 17:58