Can't view solution after contest ended

contest

#1

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

alt text

What happened?


#2

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

    INSOMB1, PAGAIN, PRIMPATT

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) :wink:


#3

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


#4

Can you please check the links. They should work now.


#5

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


#6

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


#7

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


#8

In Java you can use BigInteger.isProbablePrime(50)

here is link to my solution - http://ideone.com/wxM1jt


#9

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


#10

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


#11

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


#12

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

my c++ solution with 7 iteration got accepted :stuck_out_tongue:


#14

:smiley: lucky you!


#15

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


#16

@betlista: I passed even with isProbablePrime(10)


#17

opps… my bad…, have wrote it without confirming… sorry… my bad…


#18

Nope, ain’t working.


#19

Same here - not working still…


#20

not working