The Linear Sieve: Euler Sieve

In the deepest chamber of Prime City's brass computer, the Royal Engineer has discovered a remarkable improvement to the ancient sieve. The traditional Sieve of Eratosthenes marks each composite multiple times ÔÇö wasteful! The Euler Sieve, also known as the Linear Sieve, ensures each composite is marked exactly once, achieving O(n) time complexity. "Every composite number has a unique smallest prime factor," the engineer explains, chalk dust on her robes. "If we only mark each composite by its smallest prime factor, we visit each number exactly once. This is the elegance of the Euler Sieve." Given an integer N, find all prime numbers less than or equal to N using a linear sieve. Output them in ascending order, space-separated on a single line. The engineer's constraints: 2 <= N <= 10^7 From the engineer's test output: Input: 20 Output: 2 3 5 7 11 13 17 19 Input: 10 Output: 2 3 5 7 The brass computer hums with anticipation. The engineer has spent years perfecting this algorithm. Demonstrate its power, and the secrets of linear-time sieving will be yours to command.