3 ms·

I'd say O(n) for both. The generated list only contains primes, so that's straightforward linear. Then there is the recursive sieving, which adds an additional

I'd say O(n) for both. The generated list only contains primes, so that's straightforward linear. Then there is the recursive sieving, which adds an additional pass over the sieve list for every prime we've found so far, we need keep the computation of each pass in memory, so that's some additional memory that's also linear. The time complexity is less obvious, each prime adds an additional pass to evaluate, so that seems linear, but each new pass only applies to a list that already had all the previous passes filtered out, so that's not technically linear, but I find it hard to determine how much it actually is.

cjfd 7y ago
clearly O(n^2) for time. Well, perhaps O(n^2/log n) or something, but that is not much different. The thing is, every prime p gets passed through a filter that filters multiples of primes p' for all p' < p.
- merijnv 7y ago
  > The thing is, every prime p gets passed through a filter that filters multiples of primes p' for all p' < p But the filter for multiples of 3 only sees the values that weren't already filtered by 2. So if we have N filters we don't evaluate all N filters for each value. The 2 is applied to everything, the 3 filter is only applied to things that are not multiples of 2, the 5 filter is only applied to things that aren't multiple of 2 and 3, etc. That doesn't sound very quadratic to me.
  - cjfd 7y ago
    The thing is that the prime numbers have to go through all of the filters. Although the prime numbers are a minority among the numbers they are not a very small minority. In fact, a random number N has about a probability of 1/log(N) to be prime. So that could reduce N^2 to maybe N^2/log(N) but not any further. So I suppose the complexity actually is somewhere between N^2 and N^2/log(N), but that is not much less than N^2. The trick of only checking primes smaller than sqrt(N) reduces the complexity to N^1.5, also maybe involving some division by log(N), but that is actually an improvement in the exponent.
  - deleted 7y ago
    [deleted]

cjfd 7y ago

clearly O(n^2) for time. Well, perhaps O(n^2/log n) or something, but that is not much different. The thing is, every prime p gets passed through a filter that filters multiples of primes p' for all p' < p.

merijnv 7y ago
> The thing is, every prime p gets passed through a filter that filters multiples of primes p' for all p' < p But the filter for multiples of 3 only sees the values that weren't already filtered by 2. So if we have N filters we don't evaluate all N filters for each value. The 2 is applied to everything, the 3 filter is only applied to things that are not multiples of 2, the 5 filter is only applied to things that aren't multiple of 2 and 3, etc. That doesn't sound very quadratic to me.
- cjfd 7y ago
  The thing is that the prime numbers have to go through all of the filters. Although the prime numbers are a minority among the numbers they are not a very small minority. In fact, a random number N has about a probability of 1/log(N) to be prime. So that could reduce N^2 to maybe N^2/log(N) but not any further. So I suppose the complexity actually is somewhere between N^2 and N^2/log(N), but that is not much less than N^2. The trick of only checking primes smaller than sqrt(N) reduces the complexity to N^1.5, also maybe involving some division by log(N), but that is actually an improvement in the exponent.
- deleted 7y ago
  [deleted]