4
$\begingroup$

Suppose that I want to compute all the prime numbers between 2 and $n$. The natural way or most obvious way to do so is given below. Let $A$ is an array contain the numbers from $1$ to $n$.

  1. For $j=2$ to $j=\sqrt n$
  2. mark multiples of $j$ from $A$

Running time of this algorithm is $O(n \log n).$ It is easy to see that after first iteration there will be $n/2$ many unmarked elements and so on.

The problem with this method is that some of the elements may be marked more than one time.

Question : How to compute all the primes upto $n$ in $O(n)$ time?

$\endgroup$
  • $\begingroup$ If you only go over primes (which you can do at no cost), you improve the running time to $O(n\log\log n)$. $\endgroup$ – Yuval Filmus Feb 1 '18 at 12:56
  • $\begingroup$ Does it help if you put all elements in a (doubly)linked-list and then do the marking-trick, but instead of marking an element; you simply remove it from the list (removing can be done in $O(1)$)? This solves the "marking things twice" issue. [I am not saying that in practice; this is a good idea] $\endgroup$ – user53923 Feb 1 '18 at 13:10
  • $\begingroup$ Why would you try to mark multiples of 4? $\endgroup$ – gnasher729 Feb 1 '18 at 16:21
  • 1
    $\begingroup$ Your algorithm is a degenerated version of Eratosthenes sieve, where for each j, if j has not been marked before, you mark all its multiple. The running time is thus rougly \sum_{p prime <= n} n/p which is O(n log (log n)) (en.wikipedia.org/wiki/…): not enough but not that bad already. $\endgroup$ – holf Feb 1 '18 at 17:42
  • $\begingroup$ @gnasher729 I now notice that did not read the algorithm in the question correctly - I meant to say that you only use the elements that remain in the linked-list for the marking (smallest to largest) (since 4 is removed after doing the marking with 2; it will not be considered) $\endgroup$ – user53923 Feb 2 '18 at 9:26
5
$\begingroup$

You can use a sieve to enumerate all prime numbers up to $n$. There are multiple algorithms; see the Wikipedia article I link for some examples. The sieve of Atkin and wheel sieves apparently run in $O(n)$ time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.