I was stranded on 50.00 points for a while before I decided to explore a method similar to the sieve of Eratosthenes.
At this point, you should have derived a formula to generate the sequence of centered hexagonal numbers (A003215) and noted that the desired cuban primes (A002407) are one of its subsequences. It suffices to maintain a sieve for all the elements in the former sequence and mark those elements that are composite. To do so, you will need to solve the formula you derived modulo p and apply the Tonelli-Shanks or Bernstein algorithm to compute square roots. You will also require an implementation of the extended Euclidean algorithm to compute modular inverses.
I had to dig deep to get this, and I have to admit I think it is a very good one, going way beyond the original Project Euler problem. This link doesnt have any answers but might help to get thinking in roughly the right direction to solve for large L:
can anyone help me to decrease the time complexity of this problem?
is there is limit for value of n
how can i buy test cases for this question?
Sort 9 Discussions, By:
Please Login in order to post a comment