One fairly efficient way of solving this question is the Sieve of Eratosthenes. It will generate all primes up to ~10^6~, but the process of the sieve is more important. Essentially, the sieve works by first marking 2 as prime (p) and then all multiples of 2 as not prime (np). Then the sieve loops through all odd numbers starting from 3 and if any of these odd numbers are not already marked as np, then these must be prime. For every prime number encountered, loop through all multiples of that prime less than ~10^6~ and mark these as np.

For this question, the answer for every number is the lowest prime factor. When the sieve encounters some prime ~x~ it will mark all the multiples of ~x~ as np. It happens that in this question the first time each multiple is encountered the answer will be ~x~ itself.

Therefore when looping through the multiples of some prime ~x~ in the sieve, if the lowest prime factor is not already filled in, then the lowest prime factor will be ~x~.