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.