If you count everything carefully, it's O(n / log log n) https://www.ams.org/jou... | Hacker News

Hacker Newsnew | past | comments | ask | show | jobs | submit

hgsgm on Aug 23, 2023 | parent | context | favorite | on: My favorite prime number generator

If you count everything carefully, it's O(n / log log n)

https://www.ams.org/journals/mcom/2004-73-246/S0025-5718-03-...

They are essentially the same in all conceivable practical cases in this Universe.

log log (atoms in universe) < 100

anonymoushn on Aug 23, 2023 [–]

This seems to be a matter of the above source reporting a variation of the algorithm that is asymptotically slower than the algorithm given in the paper *and* uses asymptotically more memory. Thanks for posting the paper!

Consider applying for YC's Fall 2025 batch! Applications are open till Aug 4
Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact