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.
This problem is pretty straightforward with the observations from Problem 120. Unless the input is , we could ignore even number (where the mod is always ).
First begin with prime sieve which is large enough (half a million is more than enough) to satisfy the upper bound. As the odd mods are in increasing order, we could obtain a list of them in sorted order, then use binary search for each test case to find the answer in (I used bisect_right).
And, don't forget that is , as there is no .
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #123: Prime square remainders
You are viewing a single comment's thread. Return to all comments →
This problem is pretty straightforward with the observations from Problem 120. Unless the input is , we could ignore even number (where the mod is always ).
First begin with prime sieve which is large enough (half a million is more than enough) to satisfy the upper bound. As the odd mods are in increasing order, we could obtain a list of them in sorted order, then use binary search for each test case to find the answer in (I used
bisect_right).And, don't forget that is , as there is no .