Timeline for Efficiently finding the largest divisor of N less than sqrt(N)
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 7, 2022 at 20:22 | comment | added | Charles | @MaxAlekseyev Absolutely—if your problem is small enough just split it in two and avoid the hassle of this method. But this algorithm greatly expanded the possible range of problems to be solved. | |
| Apr 7, 2022 at 13:57 | comment | added | Max Alekseyev | The breakthrough in that paper was memory reduction, which was a big issue back in 1980s. Nowadays one can easily rely on $O(\sqrt{m})$ memory for $m\leq 2^{60}$ or so, and further memory reduction with related computational overhead is needed only for larger values, for which however the time complexity will kick in as a major limitation. | |
| Mar 22, 2022 at 17:09 | comment | added | Max | Please let me know when you succeed in implementing this! | |
| Mar 20, 2022 at 23:36 | vote | accept | Charles | ||
| Mar 18, 2022 at 3:07 | history | answered | Charles | CC BY-SA 4.0 |