 # Can't view solution after contest ended

May contest already ended, but I could not view any solution. The server keep saying: What happened?

4 Likes

How I reached the answer :

1. Wikipedia explanation:

Wikipedia explanation

2. First 500 values of totient Function : Got clear we have to print prime before n

First 500 values of Totient Function

3. Maximum gap between Prime numbers doesnt exceed 1476

Prime Gap

4. 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

5. Nice explanations of Miller Rabin test

Explanation 1

Explanation 2

Explanation 3

6. Other test may include Sieve of Eratostheness, Sieve of Atkin, AKS primality test

Seive Of Eratostheness

Seive Of Atkin

AKS Primality Test

7. 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) 4 Likes

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++

1 Like

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!!

1 Like

Same here, probably there are some background tasks to do. Also countdown for Cook-off is not displayed on main page.

1 Like

@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

1 Like

@tyrant >> In lang other than Java you can use probabilistic methods.

@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.

@tyrant >> for how many iterations were you running your Miller Rabin test?

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…

1 Like

my c++ solution with 7 iteration got accepted 1 Like 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

1 Like

@betlista: I passed even with isProbablePrime(10)