I'm practicing writing algorithms optimized for space or time complexity. With prime sieves, at minimum you must store a list of all primes found. It seems data in proportion to the number of primes found is the least amount of space such an algorithm may use.
From Wikipedia about the sieve of Atkin - What I'm unsure about is how a sieve can use O(n^1/2) space when the number of primes exceeds this. This is why it seems at minimum the space must be proportional to the number of primes. Am I confusing countable numbers with space complexity?
In this paper on the sieve of Atkin, their algorithm prints "the prime numbers up to N...Here “memory” does not include the paper used by the printer." This seems like an unfair calculation of space.
def prime_sieve(limit):
factors = dict()
primes = []
factors[4] = (2)
primes.append(2)
for n in range(3, limit + 1):
if n not in factors:
factors[n * 2] = (n)
primes.append(n)
else:
prime = factors.get(n)
m = n + prime
while m in factors:
m += prime
factors[m] = (prime)
del factors[n]
return primes
The space complexity for this algorithm is len(numbers) + len(primes); the size of the list plus the size of the dictionary.
In this case, the algorithm is worse than you'd expect for a naive prime sieve (limit). len(numbers) + len(primes) > limit because e.g. for prime_sieve(100) the following irrelevant numbers are stored in numbers:
{129: 43, 134: 67, 141: 47, 142: 71, 146: 73, 158: 79, 166: 83, 178: 89, 194: 97, 102: 17, 104: 2, 105: 3, 106: 53, 110: 11, 111: 37, 112: 7, 114: 19, 115: 23, 116: 29, 117: 13, 118: 59, 120: 5, 122: 61, 123: 41, 124: 31}
There are several prime number sieves, with varying time and space complexity; see e.g. Wikipedia and questions like How do i reduce the space complexity in Sieve of Eratosthenes to generate prime between a and b?
Also, note that there's no need for prime = numbers.get(n) - you've already checked if n not in numbers, so you can just use prime = numbers[n].