This weekend, I showed my two oldest kids how to make a Sieve of Eratosthenes. The oldest has been doing a lot of factoring, reducing fractions and decimal conversion, and it reminded me of when I learned about prime factorization. I found reducing fractions to be a lot of guess work until I understood prime factors, and using the sieve not only helped me find prime numbers, but helped me understand factorization in general.
We actually modified ours a bit, since I wanted to focus on factorization, rather than just finding a bunch of primes. On our charts, instead of crossing out the composite numbers, we wrote down the prime factor that would have led to crossing out the number in the normal sieve. This way, the kids now have a chart that shows, for all the numbers 1-100, either P for prime or the smallest factor otherwise.