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.
Project Euler #60: Prime pair sets
Project Euler #60: Prime pair sets
Sort by
recency
|
17 Discussions
|
Please Login in order to post a comment
JAva code
4, 9, 14 cash are not work
This one is very complex; in Python had to end up doing lots of optimizations. Miller-Rabin can be made deterministic beneath a certain range, it is recommended to avoid the overhead of constant random. And clique hunting is easy with set operators if you have access to them. But you have to really squeeze every ounce of efficiency from every function; there are plenty of places to prune in the clique algorithms.
I didn't end up needing multiprocessing that xperroni mentions, I didn't like the idea of processing power being the key to algorithmic optimizations for Project Euler.
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 == 1
andp2 % 3 == 2
or vice versa, then the concatenation ofp1
andp2
will be divisible by 3, and therefore(p1, p2)
is not a valid pair.Use multiprocessing to process both of the above lists simultaneously.
Solved in Python 3, time limit exceeded
Solved in Javascript, memory exceeded
Solved in javascript generating primes upto 999999 and then checking primes upto sqrt(n) in isprime() , testcase 14 failed.
What to do?
Edit: My bad, I forgot to replace "br" tag with "\n" for K=5
Same logic failed 3 test cases it python due to TLE and Javascript passed really fast. Weird
can someone help me with test case #14