Removing a number and reinserting all its multiples (by the primes in the set) into a priority queue is wrong (in the sense of the question) – i.e. it produces correct sequence but inefficiently so. It is inefficient in two ways – first, it overproduces the sequence; second, each PriorityQueue operation incurs extra cost (the … Read more
A simple fast solution in Java. Uses approach described by Anon.. Here TreeSet is just a container capable of returning smallest element in it. (No duplicates stored.) int n = 20; SortedSet<Long> next = new TreeSet<Long>(); next.add((long) 1); long cur = 0; for (int i = 0; i < n; ++i) { cur = next.first(); … Read more
If a constant factor(1) speedup counts as significant, then I can offer a significantly more efficient version: hamm :: [Integer] hamm = mrg1 hamm3 (map (2*) hamm) where hamm5 = iterate (5*) 1 hamm3 = mrg1 hamm5 (map (3*) hamm3) merge a@(x:xs) b@(y:ys) | x < y = x : merge xs b | otherwise … Read more