Matlab/Octave Eratosieve using minimal big-O iterations

Question

I'm trying to come up with ways to write Sieve of Eratosthenes in Octave that vectorize as much as possible (ie minimizing the number of times iterating over the for-loop/while-loop/recursive call)

I found one that requires only O(log(log(n))) iterations inside the for-loop, but the big-O running time (and also space) is O(n^(5/4)/log(n)) so it's arguably not the Sieve of Eratosthenes

Now I think I have one with the usual running time O(nlog(log(n))) and only O(log(n)) iterations, but I want to see if someone else comes up with a better solution.

Answer 1

Here's my solution The loop clearly runs O(logn) times and it's easy to see that the number of operations is bounded above by the normal number of operations for SOE(2n) so it's within O(nlog(logn)) big-O running time

function [primes] = eratosieve(n)
    isprime = ones(n, 1);
    isprime(1) = false;
    m = 1;
    while(m ^ 2 < n)
        nprimes = find(isprime(m + 1 : m * 2)) + m;
        mult = (m + 1) : (n/(m + 1));
        a = nprimes * mult;
        isprime(a(a<=n)) = false;
        m *= 2;
    end
    primes = find(isprime);
endfunction