Logic Challenge

To have an odd number of factors, it needs all its components to be primes raised to even powers. In other words, they're all squares. So the answer is 1000 (1, 4, 9, ... , 1000000) - that is, 1 to 1000 squared.

Why? Because the number of divisors of a number can be found as follows:
1) divide into prime factors
2) take the exponents of these, add 1
3) multiply together the results

For example,
36
1) 2^2 * 3^2
2) 3, 3
3) = 9

In order for this final product (number of divisors) to be odd, each prime has to be raised to an even power - 0, 2, 4, etc. so the second step is all odd numbers, so the third step is an odd number as well.
In other words, they're squares.

Alternatively, pair them up.

If it's a perfect square, one of the factors will be the same as its pair. If not, they'll all be different, and since they come in pairs, there must be an even number altogether.

12:
1, 12
2, 6
3, 4

16:
1, 16
2, 8
4