The Smallest Prime Factor Table

In the archives of Prime City, the Master Librarian maintains a massive ledger called the Smallest Prime Factor Table. For every number from 2 to N, the ledger records the smallest prime that divides it. This table is the foundation of countless algorithms ÔÇö prime factorization, divisor counting, and more. "The sieve can do more than just find primes," the librarian explains, adjusting her spectacles. "As you cross out multiples of each prime, you can record the prime that crossed out each number. That's the smallest prime factor. Build this table for me, and the archives will be complete." For each integer from 2 to N, output the integer and its smallest prime factor (SPF). The SPF of a prime number is itself. The librarian's constraints: 2 <= N <= 10^6 From the librarian's verified pages: Input: 10 Output: 2: 2 3: 3 4: 2 5: 5 6: 2 7: 7 8: 2 9: 3 10: 2 Input: 6 Output: 2: 2 3: 3 4: 2 5: 5 6: 2 The archives are vast, and the librarian is patient. Build the table with the efficiency of a linear sieve, and your name will be inscribed in the ledger of honor.