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.
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.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #131: Prime cube partnership
You are viewing a single comment's thread. Return to all comments →
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.