Background: Consider the integers R-n+1, R-n+2, R-n+3, ..., R. How many
of these integers are prime? Assume that R is at most n^(2+o(1)).
The standard algorithm to answer this question costs n^(2+o(1)) dollars:
it takes time n^(1+o(1)) on a general-purpose computer with n^(1+o(1))
bits of memory.
Problem: Explain how to answer the same question for n^(1.5+o(1))
dollars, using Schimmler sorting.
(There are several ways to reduce the cost even further. Some of these
ways may be covered later in the course.)