I actually have the candidates do FizzBuzz! And, it's still amazing how many people can't figure it out, or try and BS their way through it by proposing using a crazy data structure like a B-Tree (true story).
By the way, after they write FizzBuzz, ask them to modify it so that it prints "Rawr" or something if it's divisible by 7. If they printed "FizzBuzz" if it was divisible by 15, do they change their approach? If not, keep adding more strings for more prime factors until they do, or until they melt.