We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
After working on it for days, I was finally able to pass all tests using a solution written in Python 3. My tips, in spoiler order:
Skip 2 and 5 in your prime sequence, since they will never be in any valid pairs.
Use a fast prime sieve (for example this one) to generate all primes in the range first, then look for connections.
As Ki Chun TONG suggested, use the generated prime list (or rather a set, for faster search times) as the first level in your prime checker, and Miller-Rabin as the second level if the number is not found there.
Divide the generated primes into two sets primes_1 = {3} | {p for p in primes if p % 3 == 1} and primes_2 = {3} | {p for p in primes if p % 3 == 2}, then process them separately — the reason this can be done is that if p1 % 3 == 1 and p2 % 3 == 2 or vice versa, then the concatenation of p1 and p2 will be divisible by 3, and therefore (p1, p2) is not a valid pair.
Use multiprocessing to process both of the above lists simultaneously.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #60: Prime pair sets
You are viewing a single comment's thread. Return to all comments →
After working on it for days, I was finally able to pass all tests using a solution written in Python 3. My tips, in spoiler order:
Skip 2 and 5 in your prime sequence, since they will never be in any valid pairs.
Use a fast prime sieve (for example this one) to generate all primes in the range first, then look for connections.
As Ki Chun TONG suggested, use the generated prime list (or rather a set, for faster search times) as the first level in your prime checker, and Miller-Rabin as the second level if the number is not found there.
Divide the generated primes into two sets
primes_1 = {3} | {p for p in primes if p % 3 == 1}andprimes_2 = {3} | {p for p in primes if p % 3 == 2}, then process them separately — the reason this can be done is that ifp1 % 3 == 1andp2 % 3 == 2or vice versa, then the concatenation ofp1andp2will be divisible by 3, and therefore(p1, p2)is not a valid pair.Use multiprocessing to process both of the above lists simultaneously.