There is a set S of integers {1,2,⋯,100}. How many elements does the largest subset of S have so that the product of no 2 distinct elements in S is a perfect square? Prove that this is the maximum.
My idea so far is to make the subset contain 1, all the primes, all the semiprimes (numbers that are p*q where p and q are distinct primes), and all the numbers that are p*q*r where p,q,r are distinct primes. Intuitively, this seems like it would make the largest subset, but I'm not sure how to prove it.
