n=100, is the answer?
There are 25 odd prime numbers up to 102. Subtract 2 from each of these and connect the resulting numbers directly to a
2 in the middle.
For 1000, or any other values of
n, we just need to find all odd prime numbers up to
2 from them and connect each of the resultants to
2. Voila! Your tree is ready. The size of the set is simply the number of prime numbers up to
How are we sure it's a tree?
For each of the 25 elements connected to
100, we have to ensure that there are no connections between any of them, to ensure acyclicity. Since they are all odd numbers
>=3, their sum will be even and hence composite. This is sufficient to ensure that there are no edges between them.