This problem, along with the rest of the problems in the Proof for All (st)ages feature, provides an excellent context for observing, conjecturing and thinking about proof, and for appreciating the power of algebra.
Possible support
Encourage students to work in pairs and test out their ideas.
Before embarking on this problem, students could take a look at Sieve of Eratosthenes, and I Like to Prove It! (which contains a collection of more accessible problems that also challenge students to develop convincing arguments).
Possible extension
Students could be encouraged to work on the rest of the problems in the Proof for All (st)ages feature.