Can't view solution after contest ended

general
1

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

alt text

What happened?

3 Likes
2

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

1 Like
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?

4

In Java you can use BigInteger.isProbablePrime(50)

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

1 Like
5

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

6

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

7

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

8

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:

4 Likes
9

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
10

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
11

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

1 Like
12

:smiley: lucky you!

13

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
14

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

15

@betlista: I passed even with isProbablePrime(10)

16

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

17

Nope, ain’t working.

18

Same here - not working still…

19

not working

20

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.