# Using your Head is Permitted

## January 2017 solution

Yes, this is possible to do.
The basic algorithm is a classical one, known as Euler's Sieve. It is a
small optimisation over the better known Sieve of Eratosthenes, where the
improvement is that each composite is removed from the sieve exactly once.

The way to do this is by accessing a composite number *m* only when
handling its lowest prime divisor. The standard way to do this, as done by
most solvers this month, is to maintain at each point a sieve of all numbers
*m* whose smallest prime divisor is at least *p* (as is done in the
Sieve of Eratosthenes), but then to remove all numbers of the form
*p*×*m*, thus completing the next step, where the trick is
that *m* is not taken from the set of all integers but rather from those
integers that are still in the sieve at this time. The smallest value
remaining in the sieve is at each point the next prime to print out and
eliminate.

Most solutions this month did this by maintaining a linked list over the
sieve. I'd like to point out, however, a completely different implementation
of the same idea, which I received from Shizhe Zhao. Here is his algorithm.
It is based on maintaining two arrays, one ("eliminated") is the sieve
and is initialised to
all zeroes (or "false"s), and the other ("prime"), not requiring
initialisation, is the list of primes which were found. Both arrays have
indices ranging up to *n*, the number up to which
primes are to be printed. The program also maintains
a variable ("index"), indicating how many primes were printed already.

index=0;
for (int i=2; i<=n; i++) {
if (!eliminated[i]) { // i is prime
prime[index++] = i;
// print i
}
for (int j=0; j<index; j++) {
if (prime[j] * i > n) break;
eliminated[prime[j] * i] = true;
if (i % prime[j] == 0) break;
}
}

Notably, the algorithm uses no linked lists nor any other look-up accelerators,
other than the multiplication operation that forms the heart of Euler's Sieve,
appearing here as "prime[j] * i".

Because each composite is removed exactly once and each prime is visited
exactly once, the algorithm is O(*n*). In Shizhe Zhao's implementation,
this condition is maintained in a most straightforward manner: for any
*i*, the algorithm eliminates from the sieve all composites of the form
*i*×*p* with increasing prime *p* until *i* is a
multiple of *p*. Thus, one never removes such a composite by a product
where *i* has prime factors smaller than *p*. Hence,
*i*×*p* has *p* as its minimal prime factor.

Back to riddle

Back to main page