Well, I just did it. It took me about 35 minutes. I am terribly, terribly old (43 years) but I'm pretty sure I am a more than competent programmer and I have a very strong mathematical background. I was working on a laptop but a reasonably decent one, in an environment less distraction-free than an interview room but still not bad. I didn't particularly go all-out for maximum speed but wasn't gratuitously slothful.
I (deliberately) didn't use a programming language with, e.g., facilities for prime factorization built in; that would have made it much quicker but would also have made the whole thing useless as a programming test. So I had to implement the sieve of Eratosthenes, the number-of-divisors function (via prime factorization), etc.
I estimate that about 8 minutes of that time was the result of a couple of silly bugs. (It's surprising how many seconds one can lose to forgetting that 16 is less than 20.) That figure could easily have been zero or twice as much. I lost perhaps two minutes to spousal distraction.
These are all straightforward problems; in no case did I have to spend more than a few seconds thinking how to proceed, though in a couple of cases my response to having written buggy code was to replace it with something more simple-minded.
recursive, I invite you to actually sit down and implement solutions to the first 12 PE problems in, say, Python or Ruby or some similar language and tell us how comfortably under 30 minutes you come in. For the avoidance of doubt, I'm not at all saying you won't manage it -- I wasn't far off and you may very well be quicker than me. But I'll be surprised if you're so far ahead that after the exercise you still think every competent programmer should finish in at most 30 minutes.
(My rough timings for the 12 problems, in order, in minutes: 1, 1.5, 1.5, 1, 3, 1, 3, 2, 1, 4, 5, 10. These figures include bugfixing and checking against the PE site. Total lines of code: about 115.)