Time complexity of Sieve of Eratosthenes algorithm

Posted by eSKay on Stack Overflow See other posts from Stack Overflow or by eSKay
Published on 2010-04-06T05:06:23Z Indexed on 2010/04/06 5:13 UTC
Read the original article Hit count: 550

Filed under:

sieve-of-eratosthenes

|

time-complexity

|

algorithm

From Wikipedia:

The complexity of the algorithm is O(n(logn)(loglogn)) bit operations.

How do you arrive at that?

That the complexity includes the loglogn term tells me that there is a sqrt(n) somewhere.

Suppose I am running the sieve on the first 100 numbers (n = 100), assuming that marking the numbers as composite takes constant time (array implementation), the number of times we use mark_composite() would be something like

n/2 + n/3 + n/5 + n/7 + ... + n/97        =      O(n)

And to find the next prime number (for example to jump to 7 after crossing out all the numbers that are multiples of 5), the number of operations would be O(n).

So, the complexity would be O(n^2). Do you agree?

© Stack Overflow or respective owner

Related posts about sieve-of-eratosthenes

Can anyone explain segmented sieve of eratosthenes [on hold]

as seen on Programmers - Search for 'Programmers'
I've searched all over the web on implementation of segmented sieve of eratosthenes. But I found none of them suitable for a beginner. Can anyone explain me the underlying principle behind this method? EDIT: I know that in Sieve of Eratosthenes, we find all primes upto the square root of given number… >>> More
Time complexity of Sieve of Eratosthenes algorithm

as seen on Stack Overflow - Search for 'Stack Overflow'
From Wikipedia: The complexity of the algorithm is O(n(logn)(loglogn)) bit operations. How do you arrive at that? That the complexity includes the loglogn term tells me that there is a sqrt(n) somewhere. Suppose I am running the sieve on the first 100 numbers (n = 100)… >>> More
Clojure - tail recursive sieve of Eratosthenes

as seen on Stack Overflow - Search for 'Stack Overflow'
I have this implementation of the sieve of Eratosthenes in Clojure: (defn sieve [n] (loop [last-tried 2 sift (range 2 (inc n))] (if (or (nil? last-tried) (> last-tried n)) sift (let [filtered (filter #(or (= % last-tried) (< 0 (rem % last-tried))) sift)] (let… >>> More
The sieve of Eratosthenes in F#

as seen on Stack Overflow - Search for 'Stack Overflow'
I am interested in an implementation of the sieve of eratosthenes in purely functional F#. I am interested in an implementation of the actual sieve, not the naive functional implementation that isn't really the sieve, so not something like this: let rec PseudoSieve list = match list with … >>> More
Speed up bitstring/bit operations in Python?

as seen on Stack Overflow - Search for 'Stack Overflow'
I wrote a prime number generator using Sieve of Eratosthenes and Python 3.1. The code runs correctly and gracefully at 0.32 seconds on ideone.com to generate prime numbers up to 1,000,000. # from bitstring import BitString def prime_numbers(limit=1000000): '''Prime number generator. Yields the… >>> More

Related posts about time-complexity

Time complexity of Sieve of Eratosthenes algorithm

as seen on Stack Overflow - Search for 'Stack Overflow'
From Wikipedia: The complexity of the algorithm is O(n(logn)(loglogn)) bit operations. How do you arrive at that? That the complexity includes the loglogn term tells me that there is a sqrt(n) somewhere. Suppose I am running the sieve on the first 100 numbers (n = 100)… >>> More
Time complexity of a sorting algorithm

as seen on Stack Overflow - Search for 'Stack Overflow'
The two programs below get n integers from file and calculates the sum of ath to bth integers q(number of question) times. I think the upper program has worse time complexity than the lower, but I'm having problems calculating the time complexity of these two algorithms. [input sample] 5 3 5 4 3… >>> More
Time complexity for Search and Insert operation in sorted and unsorted arrays that includes duplicat

as seen on Stack Overflow - Search for 'Stack Overflow'
1-)For sorted array I have used Binary Search. We know that the worst case complexity for SEARCH operation in sorted array is O(lg N), if we use Binary Search, where N are the number of items in an array. What is the worst case complexity for the search operation in the array that includes duplicate… >>> More
Time complexity of a certain program

as seen on Stack Overflow - Search for 'Stack Overflow'
In a discussion with my friend i am not able to predict correct and tight time complexity of a program. Program is as below. /* This Function reads input array "input" and update array "output" in such a way that B[i] = index value of nearest greater value from A[i], A[i+1] ... A[n], for all i belongs… >>> More
Time complexity with bit cost

as seen on Stack Overflow - Search for 'Stack Overflow'
I think I might have completely misunderstood bit cost analysis. I'm trying to wrap my head around the concept of studying an algorithm's time complexity with respect to bit cost (instead of unit cost) and it seems to be impossible to find anything on the subject. Is this considered to be so trivial… >>> More