How to explain "why study prime numbers" to 5th Graders? I tend to teach 5th graders math ever so often just so they can be "friendly" with math in a playful manner, instead of being afraid.
However, one question that I constantly struggle with is this: Why should we care if a number is prime or not?
Coming from a computing background I try my best to explain to them the use of prime numbers in cryptography and how primes are related to factorization (as kid friendly an explanation as possible). However, they "sigh" and move on with the belief that I'm telling the truth. But, they still don't seem to get excited about it.
Answers for questions like these: Real-world applications of prime numbers? don't seem to be well suited for 5th graders.
What are some interesting ways/examples that one can use to help 5th graders understand why the study/knowledge of primes is useful? Bonus if they can "see the use" sooner in their 10 year old lifespan instead of waiting till college. 
I'm okay even conjuring "games" to help them learn/understand. For example, currently I'm trying to use something like Diffie Hellman Key Exchange to make a game for them to encode messages and see if "eavesdroppers" (i.e., other students) can guess the message. Something on the lines of Alice wants to send Bob a number that she's thinking about. Other students have to guess what that number is. The number can be 'encoded' (loosely speaking) as a manipulation of numbers similar to the key exchange protocol, but that 5th graders can play around with. Hopefully the 'decoding' process shows them why it's better to choose primes. However, this could be rather abstract. That's the best I've got for now.
Any other ideas?
 A: I may be a bit jaded, but I don't think there are a whole lot of applications that will impress someone 10 years old. I tell college students (in a class for future educators, no less!) that their ability to shop safely online depends on prime numbers, and hardly get a reaction.
So, I'd take a different approach: Mystery and intrigue.
It's hard for anyone who hasn't studied math seriously to understand what mathematics is about, but most people believe we have it pretty well figured out (and if not, the Bigger and Better Computer of Tomorrow (TM) will surely have it all straightened out in a few years, right?). Which is why it should be surprising that we really don't understand prime numbers very well! 
That's a bit of a stretch, of course. We know a lot about prime numbers, but the biggest (or at least most famous) open question in all of mathematics, the Riemann Hypothesis (I wouldn't even mention the name, let alone give any details!) is a belief about prime numbers. Another big-hitter (again, fame-wise; I can't fathom why it would be important to anyone) is the Goldbach Conjecture, another belief concerning prime numbers. This one could easily be stated to 5th graders, and they could verify that it's true for any numbers they pick out.  
If the million dollar bounty for the Riemann Hypothesis is still in effect and you knew everything there was to know about prime numbers, you'd walk away with a cool million dollars! That's how much more we want to know about prime numbers, because we just don't know certain things!
The point is this. It's easy to define a prime number, and easy to work with prime numbers. But when we start asking certain questions, we just don't know. Nobody does. A handful of incredible mathematicians know a bit more than most, but even the most well-informed people on earth only know incrementally more than your students, when it comes to prime numbers. (Again: obviously a stretch. This really applies to isolated statements about prime numbers, but we're trying to sell here, not be pedantic).

I'll also mention that when we talked about the Sieve of Eratosthenes for finding prime numbers (again in the class for future educators), I remarked that this method is over two-thousand years old (older than many popular Western religions). Fast forward to now, and our best methods for listing all prime numbers in a certain range are only incrementally better. Cooler still, these better methods all use this basic sieving technique at their core! So we're better at listing primes because we're better at sieving, but not that much better -- in two thousand years! 
Your 5th graders could easily sieve, and use the primes they find to verify Goldbach's Conjecture for tons of numbers. They'd be playing the game of mathematics then, getting their hands dirty in a completely self-sufficient way. And it can be phrased as a challenge: "I bet you can't write 138 as a sum of two primes!"
So the big moral of the story is that, to mathematicians, primes are mysterious, shiny objects. I wouldn't focus on their shininess, only the mystery. They have such mysterious facets that, in some ways, we're not much better at understanding them than we were thousands of years ago. 
A: I can tell, without doing any calculations, that
$$31\cdot 23\neq 37\cdot 19.$$
It follows from the unique factorization of integers into prime numbers, and I know that all four numbers are primes.
A: Donald Knuth said, "virtually every theorem in elementary number theory arises in a natural, motivated way in connection with the problem of making computers do high-speed numerical calculations"
When I try to explain the so what in what I do, I often start there. The reason I study algorithms and mathematics is because I find it beautiful and interesting but it has a practical effect of making my computer do something a lot faster. Everyone likes faster computers.
To be honest, sometimes the beauty is found in the speed alone.
A: Here's another suggestion. Have some of the students (maybe $5$ or so) play a again. The purpose of the game is to end up with the lowest possible score.
Each student pick a number between $30$ and $40$. Maybe they pick $31, 32, 35, 37, 39$.
The game is to go through all the integers from $1$ to $40$, and each time an integer divides a student's number, that student gets a point. Of course the students with prime numbers will end up with only two points and will win the game.
This does not answer the question of why we should care about prime numbers (oh, to win the game of course!), but might lead to a better understanding or a bigger interest in primes.
