I'll add another different suggestion to that of my first if you'll allow.
What about some sort of timeline of primes discovered with some nice caricatures of how they might have been discovered?
As user ajotatxe remarked:
This idea requires a person who has some talent for art. I don't have it.
This also applies to me but I'll give it a shot.
For example, you might initially have some people counting with their hands, or scribbling on paper, (actually show a few prime numbers), maybe even a sort of sieve like others suggested but I wouldn't want to rob their ideas, or some feint marks resembling modular calculations. A few random guesses for the Mersenne Numbers which were thought to be prime, question marks and maybe even one or two of the smaller ones with question marks.
Maybe move onto some inkling of Lucas and Lehmer's method and/or others, which I don't claim to have read/be any sort of expert in.
You can top it off with an effective "comical" drawing of asking a computer, is such a number prime, and it say "true", maybe even with an implied "ding" just for effect :)