Computational Complexity
This sieve computes primes up to N using O(N/log log N) operations with only N1/2 + o(1) bits of memory. That is a little better than the sieve of Eratosthenes which uses O(N) operations and O(N1/2(log log N)/log N) bits of memory. These asymptotic computational complexities include simple optimizations, such as wheel factorization, and splitting the computation to smaller blocks.
Read more about this topic: Sieve Of Atkin
Famous quotes containing the word complexity:
“In times like ours, where the growing complexity of life leaves us barely the time to read the newspapers, where the map of Europe has endured profound rearrangements and is perhaps on the brink of enduring yet others, where so many threatening and new problems appear everywhere, you will admit it may be demanded of a writer that he be more than a fine wit who makes us forget in idle and byzantine discussions on the merits of pure form ...”
—Marcel Proust (1871–1922)