Return to Question

I have several questions regarding the analysis, behaviour, and expression of a simple sieving algorithm which uses associative arrays. The pseudocode below assumes integer addition, string concatenation, checking that an index (key) exists in an array (so at the beginning, (n in c) is false for all n, but when c[m]=p is carried out, then (m in c) returns true), and sufficient memory. (Or set LIM to 100.)

Edit 2018.08.08 This answer https://mathoverflow.net/a/307881 will be updated to give recent information about S, especially a forthcoming preprint. End Edit 2018.08.08

I have several questions regarding the analysis, behaviour, and expression of a simple sieving algorithm which uses associative arrays. The pseudocode below assumes integer addition, string concatenation, checking that an index (key) exists in an array (so at the beginning, (n in c) is false for all n, but when c[m]=p is carried out, then (m in c) returns true), and sufficient memory. (Or set LIM to 100.)

I have several questions regarding the analysis, behaviour, and expression of a simple sieving algorithm which uses associative arrays. The pseudocode below assumes integer addition, string concatenation, checking that an index (key) exists in an array (so at the beginning, (n in c) is false for all n, but when c[m]=p is carried out, then (m in c) returns true), and sufficient memory. (Or set LIM to 100.)

Update 2017.08.28: I am still looking for references. I have posted a request to https://cs.stackexchange.com/q/79971 which includes some literature references I found which are of interest but still miss the mark for this question. End Update.

I have several questions regarding the analysis, behaviour, and expression of a simple sieving algorithm which uses associative arrays. The pseudocode below assumes integer addition, string concatenation, checking that an index (key) exists in an array (so at the beginning, (n in c) is false for all n, but when c[m]=p is carried out, then (m in c) returns true), and sufficient memory. (Or set LIM to 100.)

(Compare a similar algorithm which in part computes the list of distinct prime factors for each n, found here: http://mathoverflow.net/a/50691 .) When this loop is run, at the end c[m] contains a prime factor p of m for each composite number m at most LIM, as well as for some composite m greater than LIM. t contains for each p a comma-delimited string of indices m for which c[m] gets p. It is a nice exercise to show that (at the end of the loop body) p is a prime, that c has only composite indices m, that c[m] when defined is always a prime dividing m, and that t[p] encodes an increasing sequence of some multiples of p. When I simulate this by hand, I imagine the primes p jumping over occupied slots in c until they find an empty slot c[m] and land there.

(Compare a similar algorithm which in part computes the list of distinct prime factors for each n, found here: https://mathoverflow.net/a/50691 .) When this loop is run, at the end c[m] contains a prime factor p of m for each composite number m at most LIM, as well as for some composite m greater than LIM. t contains for each p a comma-delimited string of indices m for which c[m] gets p. It is a nice exercise to show that (at the end of the loop body) p is a prime, that c has only composite indices m, that c[m] when defined is always a prime dividing m, and that t[p] encodes an increasing sequence of some multiples of p. When I simulate this by hand, I imagine the primes p jumping over occupied slots in c until they find an empty slot c[m] and land there.