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.
Around 2 seconds for T = 100000 and max L = 25 * 10^12.
The key to solve is to generate cuban primes efficiently and then use binary search for each query. In order to generate cuban primes efficiently I used a sieve for n. Sieve is indexed by n and maximum length is determined by maximum L. For every prime up to L^0.5 starting from 5 I solved quadratic congruence 3 * n^2(n + 1) + 1 = 0 (mod prime) using Tonelli-Shanks algorithm and calculating inverse modulo using extended Euclidean algorithm.
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 →
Around 2 seconds for T = 100000 and max L = 25 * 10^12. The key to solve is to generate cuban primes efficiently and then use binary search for each query. In order to generate cuban primes efficiently I used a sieve for n. Sieve is indexed by n and maximum length is determined by maximum L. For every prime up to L^0.5 starting from 5 I solved quadratic congruence 3 * n^2(n + 1) + 1 = 0 (mod prime) using Tonelli-Shanks algorithm and calculating inverse modulo using extended Euclidean algorithm.