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?
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.
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!!
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.
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…
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