You are not logged in. Please login at www.codechef.com to post your questions!

×

Can't view solution after contest ended

4
1

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

alt text

What happened?

asked 13 May '13, 16:05

tyrant's gravatar image

2★tyrant
1.2k202734
accept rate: 12%

edited 13 May '13, 16:07

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 ♦♦3★

@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) betlista ♦♦3★

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

(13 May '13, 16:15) bugkiller3★

@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) bugkiller3★

@betlista: I passed even with isProbablePrime(10)

(13 May '13, 16:42) sanchit_h6★
showing 5 of 7 show all

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) ;)

link

answered 13 May '13, 16:28

devanshug's gravatar image

4★devanshug
2.7k111927
accept rate: 13%

edited 13 May '13, 16:43

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) betlista ♦♦3★
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) bugkiller3★

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

(13 May '13, 16:42) devanshug4★

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

link

answered 13 May '13, 16:33

bugkiller's gravatar image

3★bugkiller
8.7k194898
accept rate: 9%

edited 13 May '13, 16:38

1

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

(13 May '13, 16:36) kuldeepfouzdar3★

:D lucky you!

(13 May '13, 16:37) bugkiller3★

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

link

answered 13 May '13, 16:50

tijoforyou's gravatar image

2★tijoforyou
4.2k52364
accept rate: 15%

edited 13 May '13, 16:58

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

link

answered 13 May '13, 16:42

abhijeetpandey's gravatar image

3★abhijeetpandey ♦♦
45471013
accept rate: 22%

Nope, ain't working.

(13 May '13, 16:43) bugkiller3★

Same here - not working still...

(13 May '13, 16:47) betlista ♦♦3★

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) bugkiller3★

now fixed!

(13 May '13, 16:52) bugkiller3★

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) styagi2809942★

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) betlista ♦♦3★

Links for JUNONGF not working, please fix it...

(13 May '13, 17:58) styagi2809942★
showing 5 of 9 show all
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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