This is my entry to the contest organized by @grider123 here.
If you're going to participate maybe don't read this yet, otherwise you're kind of spoiling yourself part of the fun ^^".
Anyways, my answer in GolfScript is this:
[2 3 5 7]?-1>'YES''NO'if
And you can see it working here with some sample inputs. Sorry about the printing format of the results (no line jumps ^^").
Now to explain the process and the solution a bit.
At first, I started thinking about how to detect Harshad numbers on one hand, and prime numbers in the ]0, 2000[ range on the other hand. I'm a C++ guy, so I started to think about solving it in C++ or maybe Python or Lua. Of course that was going to be verbose as hell compared to GolfScript, but at this point I still thought I had a kind of difficult problem on my hands.
And then, this morning, doing something completely unrelated, it hit me. Unless I'm completely missing the mark or misenterpreting something, in which case you're going to get a great laugh out of this, this is one of those "trick question" problems. And one problem where "divide and conquer" (i.e. solve the two smaller problems first then combine) is actually a terrible idea.
Let's look closely at our two conditions:
- Needs to be a prime number. Defined as: A prime number is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers.
- Needs to be a Harshad number. Which means that "can be divided by the sum of its digits".
Now, we can rephrase the prime number definition to: a number that cannot be divided by two smaller natural numbers, i.e. can only be divided by itself and 1.
So after "translating" we're left with these conditions:
- Can only be divided by itself and 1.
- Can be devided by the sum of its digits.
Which means that we only have to return YES for prime numbers that have a single digit, because any other number that it's divisible by the sum of its digits is, by definition, not a prime number. Knowing this we can just hardcode the numbers, do a search in the hardcoded array, and return depending on the result.
In pseudocode it looks something like:
if find(X, [2, 3, 5, 7]):
return 'YES'
else:
return 'NO'
And of course I'm enough of a geek to decide that, having such an "easy" answer, I wanted to learn enough GolfScript to be able to write it :)
I hope you found this entry interesting, and I really hope I win the contest, even if I'm kind of shooting myself in the foot by giving such a detailed explanation XD. Still, good luck to any other participants, and have fun ^^