I don't see the WTF in this. I was expecting a hate filled life threatening coffee disrupting termination mail reply. Instead all I got to see was a professional response.

MightyM2012-11-08 08:09

Whats wrong with the code? Works for all my testcases.

¯\(°_o)/¯ I DUNNO LOL2012-11-08 08:17

It's his loss for not hiring such a brillant programmer as Boris.

Smug Unix User2012-11-08 08:19

Perhaps Float would have been better?

Migala2012-11-08 08:20

Clearly the WTF is to keep asking Boris to submit code when there is already more then enough to base a decision on. Right?

PedanticCurmudgeon2012-11-08 08:29

Doctor_of_Ineptitude:

I don't see the WTF in this. I was expecting a hate filled life threatening coffee disrupting termination mail reply. Instead all I got to see was a professional response.

Actually, the WTF is Phil, whose take-home assignment only measures the candidate's ability to use google.

the beholder2012-11-08 08:36

PedanticCurmudgeon:

Doctor_of_Ineptitude:

I don't see the WTF in this. I was expecting a hate filled life threatening coffee disrupting termination mail reply. Instead all I got to see was a professional response.

Actually, the WTF is Phil, whose take-home assignment only measures the candidate's ability to use google.

Maybe this story was from a time before Google?

Heck, how did people like Boris kept themselves from starving back then?

ColdHeart2012-11-08 08:44

And if they fail to do that, is it really worth going on? It's not a bad test.

1. They don't use google and produce bad code. Fail.
2. They don't use google but manage to produce (potentially weak) code that solves the problem. Pass.
3. They use google and still produce bad code. Fail.
4. They use google and come up with a good solution. Pass.

You can then test them further if you want to, but it gives a good baseline of their ability to solve a problem. They either know the subject area already, or research it to find the solution. Either way, if they solve the problem with good code then they are on the right path.

PedanticCurmudgeon2012-11-08 08:46

the beholder:

PedanticCurmudgeon:

Actually, the WTF is Phil, whose take-home assignment only measures the candidate's ability to use google.

Maybe this story was from a time before Google?

Heck, how did people like Boris kept themselves from starving back then?

Not sure if troll or comprehension fail.....

Remy Porter2012-11-08 08:48

If someone gave me this "homework", the first thing I'd ask would be, "Do you just want a naive implementation, or should I use a more efficient algorithm? If you want the simple approach, I could rip that out right now."

dkf2012-11-08 08:52

PedanticCurmudgeon:

Actually, the WTF is Phil, whose take-home assignment only measures the candidate's ability to use google.

Doesn't matter. It's worked perfectly in this case, in that while Boris's first attempt was just rather poor, his second band-aid around it was stunningly bad and a clear demonstration that he shouldn't be hired.

Except by whichever place maintains phpMyAdmin. Boris would definitely raise standards there.

YeahThatGuy2012-11-08 08:55

PedanticCurmudgeon:

Doctor_of_Ineptitude:

I don't see the WTF in this. I was expecting a hate filled life threatening coffee disrupting termination mail reply. Instead all I got to see was a professional response.

Actually, the WTF is Phil, whose take-home assignment only measures the candidate's ability to use google.

You are right! That will be a massive problem when you hire him and he's not allowed an internet connection!

You can make it slightly more efficient by breaking the loop at $val / 2, since you've already divided by 2 by the time you get there.

MightyM2012-11-08 09:12

Remy Porter:

You can make it slightly more efficient by breaking the loop at $val / 2, since you've already divided by 2 by the time you get there.

Actually you only need to iterate to the squareroot of $val.

urza98142012-11-08 09:12

Remy Porter:

You can make it slightly more efficient by breaking the loop at $val / 2, since you've already divided by 2 by the time you get there.

You can make it FAR more efficient by using the square root. Anything larger than that would have to be multiplied by something smaller than that, which you would have already tested.

Rodnas2012-11-08 09:13

Before you star developers are all going to show us minor gods how it is done... i did what any sane programmer would do and searched the internet for an answer.

All i found was inefficient code. Well it is better than no code at all

Anoldhacker2012-11-08 09:14

Remy Porter:

You can make it slightly more efficient by breaking the loop at $val / 2, since you've already divided by 2 by the time you get there.

And by slightly, we mean REALLY slightly. The classic first improvement is to stop at sqrt($val). It starts to get more interesting after that.

Rnd(2012-11-08 09:15

urza9814:

Remy Porter:

You can make it slightly more efficient by breaking the loop at $val / 2, since you've already divided by 2 by the time you get there.

You can make it FAR more efficient by using the square root. Anything larger than that would have to be multiplied by something smaller than that, which you would have already tested.

Test the oddity and start 3 and add increase by 2 each time.

Or am I wrong with this? Should't it about double efficiency?

I'm just a noob though...

Cbuttius2012-11-08 09:15

I think giving a programming exercise is a much better idea than judging by ability to answer well in an interview situation.

The real WTF is that the programming exercise was not the first step. There were probably many candidates who were rejected at the CV stage who would have passed that test easily.

Remy Porter2012-11-08 09:16

Even better. I was napkinning in my head- the last time I wrote a prime number function was in high school. I've read up on some of the more interesting algorithms, but I couldn't implement one without further research.

Cbuttius2012-11-08 09:16

why has nobody posted yet that the real WTF is PHP?

Rnd(2012-11-08 09:17

Cbuttius:

why has nobody posted yet that the real WTF is PHP?

Because that one is too obvious?

Still, PHP instead of C... Doctored CV?

Cbuttius2012-11-08 09:39

And once when I wrote one, I tested if the number was greater than 5. Then tested divisbility only for numbers with mod 30 that were:

1, 7, 11, 13, 17, 19, 23, 29

so only 8 numbers out of every 30.

Incidentally I have my own formula for calcuating if numbers are prime, which I usually use for 4 digit numbers and it involves performing modulo arithmetic by certain numbers, then resolving as a difference of two squares. If the number can be resolved as such a way it is not prime, if it cannot then it is.

Example number 4769. We normally test divisibility first by 2, 3, 5, 7, 11 and 13. You can go a bit further with the normal method. In any case it is clear that the number is not divisible by 2, 3 or 5. With regards to the next 3 we can reduce with the 1001 rule, so we reduce to 765 which we can quickly deduce is not divisible by any of those 3.

Now we look at the modulo arithmetic of the number.

- 8 mod 9. That means it would be the difference of a number divisible by 9 and one whose square is 1 mod 9. In any case we normally look at the upper number in the difference, so we are looking for a number divisible by 3.

- 1 mod 8. So the upper number must be odd.

- 4 mod 5. Upper number may be divisible by 5, otherwise we can go further and say its 12 or 13 mod 25. Quite a reduction.

- 2 mod 7. Squares mod 7 are 0, 1, 2, 4 so the number must square to a 2 or a 4. That means it cannot be divisible by 7 or 1 or -1 mod 7.

Looking at the square root of the number we have, it's above 69.

The first number that passes all our tests is 75, then 87, then there are none until 135.

5625-4769 is 856 which isn't square. The square root of this value is around 29 so we can already say we've resolved all possibly prime factors up to 41.

87 squared is 8100-540+9 = 7569. Subtract 4769 and you get 2800 which isn't square either. Now we've got a bit further though, sqrt(2800) is approximately 53 so solved up to 34. Ok not much progress, only ruled out 37.

However our next effort is 135:

135 squared is 18225. Subtract 4769 is 13456, and we can actually work out this is 116 squared... So we've found the solution, 4769 is divisible by 19 (multiplied by 251, the sum of 135 and 116).

Phil2012-11-08 09:43

Phil here; the interview took place around 2000 so Google were around but not quite as pervasive as they are today. My expectation was that he would use Google or similar to discover what algorithms are out there and then implement one or more of them.

I actually had drawn on my own prior experience of a telephone interview where my prospective employer was in a different country. I was quite inexperienced and didn't have much to show as sample code so they asked me to submit an implementation of a test for primeness. I thought this was quite a good assignment as there is an easy solution (sieve of Eratosthenes) and then various more complex but efficient solutions.

In my case, I got an implementation of "sieve" working quite quickly and then got to work on another algorithm from Applied Cryptography (I don't remember the name). My submission included both implementations with an explanation of each including a reference to Applied Cryptography which I thought would impress them (it turned out the interviewer hadn't heard of Bruce Schneier despite being in the crypto field, wtf!)

In the end, they didn't offer me the job but I thought I'd keep it in mind as a good programming assignment to test if someone is:

1. capable of implementing a basic algorithm
2. inclined to do a bit of research (googling) to see if there is something better out there

Anyway, Boris failed miserably but I wanted to have a rock solid case against hiring him as others in the company were keen to get him in regardless so that's why I gave him a second chance. What's missing from the story is that after my response to his second submission, he asked if the work would be billable; that was when we asked him (nicely) to please go away.

StupidTheKid2012-11-08 09:45

Hum, you realize that making an efficient prime number detector for all possible values is currently impossible. The difficulty of finding prime numbers is what makes RSA secure after all... Okay, one guy claimed to have solved it, but his proof takes a hundred pages and is still under review :

I though the real WTF was that his checkInteger implementation is O(n) (if I read the PHP correctly).

Phil2012-11-08 09:54

If I remember correctly, the algorithm in Applied Cryptography is a fast way of getting what is probably the right answer as long as you can stand a few false negatives (so it might tell you that your prime number isn't prime but not vice versa). I could be wrong, it's a long time ago and I have never had to look at it since.

JC2012-11-08 10:00

"Hum, you realize that making an efficient prime number detector for all possible values is currently impossible."

No, factorizing* prime numbers is what is neigh-on impossible. Determining if any given number is a prime is very much possible.

* "Prime Factorization" is finding which prime numbers multiply together to make the original number.

Anonymous2012-11-08 10:01

Rnd(:

urza9814:

Remy Porter:

You can make it slightly more efficient by breaking the loop at $val / 2, since you've already divided by 2 by the time you get there.

You can make it FAR more efficient by using the square root. Anything larger than that would have to be multiplied by something smaller than that, which you would have already tested.

Test the oddity and start 3 and add increase by 2 each time.

Or am I wrong with this? Should't it about double efficiency?

I'm just a noob though...

Using square root of the number as a limit makes a big difference when the prime candidates starts to grow.

Take the number 99999997 as an example. Say you only check odd number until you reach number/2. You have now tested about 25 million numbers and you know you found a prime! However, if you use square root as a limit you only need to test about 10000 numbers. Of course you only need to check the odd ones so then you are down to 5000.

Anonymous Paranoiac2012-11-08 10:12

b_russel:

I though the real WTF was that his checkInteger implementation is O(n) (if I read the PHP correctly).

Yeah, I was about to say that just his checkInteger() function should have been more than enough to disqualify him as it is possibly the least efficient way of calculating it. Even if you ignore native PHP methods for determining type (is_int() comes to mind), you could write an integer checker much more simply by just doing this:

The nice thing about recursion is that you get to use recursion.

I, too, was recently given the prime number test during an interview. Well the last time I did that was 32 years ago in Fortran. And I usually don't write code on a whiteboard with someone watching me. I'll stub out the structure (loops etc.) then go back and fill in the details.

So, anyway, I didn't get the job. Never mind that I could have helped them secure their website, and the guy they hired apparently can't, because it is still penetrable. At least he could rattle off an algorithm during an interview.

Claxon2012-11-08 10:16

It makes you wonder how people can avoid thinking "Hmmm, determining if a number is an integer. I wonder if anyone has done this before?"

He could have HALVED the amount of code just by using PHP's is_int() function.

That's enough of a reason to stop reading and fail his test right there.

Matt2012-11-08 10:17

This smacks of someone who had too much math and not enough sense. The "beauty" of integers is that you can define an almost-infinite sequence of them recursively with only the postulates of "one" and "plus". So, naturally, that's how he tested whether the input was a member of the set of integers.

Rnd(2012-11-08 10:17

Anonymous:

Rnd(:

urza9814:

Remy Porter:

You can make it slightly more efficient by breaking the loop at $val / 2, since you've already divided by 2 by the time you get there.

You can make it FAR more efficient by using the square root. Anything larger than that would have to be multiplied by something smaller than that, which you would have already tested.

Test the oddity and start 3 and add increase by 2 each time.

Or am I wrong with this? Should't it about double efficiency?

I'm just a noob though...

Using square root of the number as a limit makes a big difference when the prime candidates starts to grow.

Take the number 99999997 as an example. Say you only check odd number until you reach number/2. You have now tested about 25 million numbers and you know you found a prime! However, if you use square root as a limit you only need to test about 10000 numbers. Of course you only need to check the odd ones so then you are down to 5000.

Pretty much meant further optimisation. There is a why more tricks I think, but at some point it's better to move to some more specialised algorithms.

Anyway anyone got prime test which uses no extra memory or minimal amount of it?

MBA2012-11-08 10:19

Hey, if it passes the test cases it's production code. Ship it!

Any post-launch issues can be dealt with by the bug fixers. We could probably even charge extra for the performance upgrade.

Tom2012-11-08 10:22

Rnd(:

Pretty much meant further optimisation. There is a why more tricks I think

Some speak confuse not born country language maybe translation google mud said him meant?

Larry2012-11-08 10:24

He may still be learning indentation but at least he's consistent with his use of:

}
else
{

Now if I could only figured out what he hoped to accomplish with:

"
\n");

Mark2012-11-08 10:29

Phil:

What's missing from the story is that after my response to his second submission, he asked if the work would be billable; that was when we asked him (nicely) to please go away.

Ah, Boris was actually demonstrating his ability to do consulting in the real world. On the 3rd or 4th time upgrading this function, after much time billed and wasted, he would then give you something that worked. I bet Boris went far.

Cbuttius2012-11-08 10:29

A lot depends on whether you want to test just one number of primeness or build a machine that will test the primeness of many numbers.

To do the latter, build a prime number table.

To build a prime number table up to N, mark every cell with itself. You can of course make the table size N-1 as we don't test 0 or 1 for primeness.

Take the first prime number which is 2. You now mark every product of 2 with the number 2. Next is 3: You know this is prime because it's still marked with a 3. You jump to its square and mark every 3rd number that currently has itself as the value with a 3.

4 is marked as non-prime so continue with 5.

Once we get to a value where the square is beyond N we stop and we have our prime number table. Then constant time to check if a number it contains is prime or not.

If we want to check the primeness of a number beyond the table, we at least know what the primes are so we know what values to try modding it by, so more efficient in those numbers too.

Anoldhacker2012-11-08 10:32

Phil:

If I remember correctly, the algorithm in Applied Cryptography is a fast way of getting what is probably the right answer as long as you can stand a few false negatives (so it might tell you that your prime number isn't prime but not vice versa). I could be wrong, it's a long time ago and I have never had to look at it since.

So, you check if Fermat's Little Theorem holds for the possible prime with a few candidates. If not, it fails. If so, then it starts to look like it might be prime.... http://en.wikipedia.org/wiki/Primality_test

In crypto, you are usually just looking for SOME prime number, not a definite statement about a particular number. In that case, a false negative usually not a problem.

Matthijs2012-11-08 10:34

Claxon:

He could have HALVED the amount of code just by using PHP's is_int() function.

Bear in mind that the candidate proclaimed to have little or no knowledge of PHP, and was only using that language to expand his programming abilities; a very commendable effort in and of itself.

Not to mention, this was 2000; PHP 4 (which first included is_int() and is_numeric()) was released only halfway through that year, so he may have well used PHP 3.

Last but not least: those of us working with PHP for a long time know that the language can do pretty much anything for you, natively. But people used to languages like C start of with the assumption that by default your language has about two tools, and everything else needs to be loaded from libraries. After a while, a PHP's programmer first instinct when faced with a new problem will be to search if there is a default function available to do that, but it takes time before that mindset is achieved.

Brent2012-11-08 10:37

Remy Porter:

If someone gave me this "homework", the first thing I'd ask would be, "Do you just want a naive implementation, or should I use a more efficient algorithm? If you want the simple approach, I could rip that out right now."

That's a very important thing to do. I have a friend that when asked to do the Fibonacci Sequence, proceeded to quickly work out the closed form expression and coded that. This confused the interviewers to no end.

PedanticCurmudgeon2012-11-08 10:39

Phil:

Anyway, Boris failed miserably but I wanted to have a rock solid case against hiring him as others in the company were keen to get him in regardless so that's why I gave him a second chance.

So TRWTF was left out of the article entirely. How typical.

Rnd(2012-11-08 10:41

Tom:

Rnd(:

Pretty much meant further optimisation. There is a why more tricks I think

Some speak confuse not born country language maybe translation google mud said him meant?

I got to code some C so I obfuscate my comments ;D Just use preprocessor to remove why ;D

Lordy2012-11-08 10:42

checkDouble(-0.5) .. thinking ...

neminem2012-11-08 10:42

For the job I'm at, I had a similar experience - after the usual silly discussion questions, they gave me a couple really small programming questions, that I think I did a decent job of. Then they asked me a larger one - convert an int to its roman numeral expansion (or possibly the reverse, I forget, it was a while ago). That is the sort of problem domain I would not have had any reason to be an expert in before being asked to solve it, and my first response in a real scenario would clearly be visiting wikipedia for what the full rules of roman numerals even were. I had to ask a bunch of questions. So they said just go home, write it and email it. Interview ended at around 5 PM, I had it to them by 8 the next morning. It definitely would not have been nearly such a nice experience if I'd had to do the whole thing writing on a whiteboard with no internet.

Giving a whole week seems needlessly nice, though.

hikari2012-11-08 10:49

I don't mind questions like this, so long as they're not "and do it right now in the interview" ones.

I think I would have just gone and looked up an algorithm on-line or in one of my books - one of them is bound to have one in - and then implemented it.

I have a similar reaction to interviews as the candidate in the story; I end up talking in a muted whisper, sweating, and shaking. Sometimes in life I get lucky and interview with people who can see through this (like my current employers). Having people who are willing to make effort to interview people like us makes me really rather appreciative.

DCRoss2012-11-08 10:50

Anonymous:

Take the number 99999997 as an example. Say you only check odd number until you reach number/2. You have now tested about 25 million numbers and you know you found a prime! However, if you use square root as a limit you only need to test about 10000 numbers. Of course you only need to check the odd ones so then you are down to 5000.

If you want to get picky, you only need to check the factors which are prime themselves. As long as you have a fresh supply of interview candidates and undergrad students to provide you with lists of primes that cuts it down further to just over 1000.

Cbuttius2012-11-08 10:53

Anonymous:

Take the number 99999997 as an example. Say you only check odd number until you reach number/2. You have now tested about 25 million numbers and you know you found a prime! However, if you use square root as a limit you only need to test about 10000 numbers. Of course you only need to check the odd ones so then you are down to 5000.

Or I might get as far as 1297 and discover that it is not prime. (1297 * 77101)

captcha:augue2012-11-08 10:54

So you got experience with C and embedded systems? Great, you're the perfect candidate for our PHP job!

The other way around would be a much bigger WTF of course, but it's still a waste of a low-level programmer.

hikari2012-11-08 10:55

neminem:

For the job I'm at, I had a similar experience - after the usual silly discussion questions, they gave me a couple really small programming questions, that I think I did a decent job of. Then they asked me a larger one - convert an int to its roman numeral expansion (or possibly the reverse, I forget, it was a while ago). That is the sort of problem domain I would not have had any reason to be an expert in before being asked to solve it, and my first response in a real scenario would clearly be visiting wikipedia for what the full rules of roman numerals even were. I had to ask a bunch of questions. So they said just go home, write it and email it. Interview ended at around 5 PM, I had it to them by 8 the next morning. It definitely would not have been nearly such a nice experience if I'd had to do the whole thing writing on a whiteboard with no internet.

Giving a whole week seems needlessly nice, though.

Roman numerals give you fun problems anyway. There's never been a formal way of writing them; clocks, for example, tend to use IIII for 4, whereas people will tend to write it as IV.

Tim2012-11-08 10:57

Well obviously he should have called out to a web service using XML. There must be one somewhere that can tell you if a given number is prime.

Just hope it isn't encrypted over https. Because in setting up the crypto you'll probably need some prime numbers! Recursion lurks wherever you look. If you don't see it at first, look closer.

Caesar2012-11-08 10:59

hikari:

Roman numerals give you fun problems anyway. There's never been a formal way of writing them; clocks, for example, tend to use IIII for 4, whereas people will tend to write it as IV.

Roman numerals were invented by people who had to chisel them in stone. There's no way you'd chop away at "IIII" when you could simply do "IV".

David F. Skoll2012-11-08 11:05

When asked to prove that all odd numbers greather than two are prime:

The mathematician said: "3 is prime, 5 is prime, 7 is prime, ... and so on."

The engineer said: "3 is prime, 5 is prime, 7 is prime, 9 is experimental error, 11 is prime..."

The arts major said: "What does 'prime' mean?"

Coyne2012-11-08 11:13

Man, why are we fiddling with all this Mersenne stuff?! According to him we can have 100,000 digit primes just by checking MOD 2, 3, 5 and 7!

Joe2012-11-08 11:13

hikari:

Roman numerals give you fun problems anyway. There's never been a formal way of writing them; clocks, for example, tend to use IIII for 4, whereas people will tend to write it as IV.

Yes, which is why I write all my algorithms to accept input in "Simplified Roman Numerals"-- None of this "VXLCM" nonsense, just give me "IIIIIIIIIIII" for 12.

It also has the benefit of making those pesky NP-hard problems run in polynomial time (of the length of the input)

--Joe

jas882012-11-08 11:15

JC:

No, factorizing* prime numbers is what is neigh-on impossible.

No, factorising *prime* numbers is very easy ... by definition, the sole factor is the number itself. It's factorising large NON-prime numbers that gets tricky, and that's the bit that's needed for breaking public-key crypto systems like RSA.

Cbuttius2012-11-08 11:25

PHP is an extendable language. Knowledge of C would be good because you can write your extensions in it.

lethalronin272012-11-08 11:35

At least he was honest. His crap code DOES represent his work very well.

It doesn't really matter if the prime test is correct. This is an interview to see if the guy can code. So judge the code, not the algorithm. There is plenty of evidence in the first sample (which worked for a small set of numbers) that the coding is sloppy and misguided.

Only if the code is good should you even consider looking at if the algorithm is good.

My other thought was, even if they guy's code was great, would you hire him after such a bad interview? If his code was great, and you turned him down, you could be in a whole lot of bother if he challenged the decision any the grounds of any form of discrimination he chooses as your only hard evidence is a good piece of code!

verisimilidude2012-11-08 11:43

if (($Number > 0) AND ($Number < 1))
{
return (FALSE)
}
else
{
return (TRUE)
}

I see his level of expertise right there. If he can't do

return ($Number > 0) AND ($Number < 1)

then his code it too wordy for consideration.

JJ2012-11-08 12:00

JC:

No, factorizing* prime numbers is what is neigh-on impossible.

Said the horse.

Not Badinoff2012-11-08 12:03

PedanticCurmudgeon:

Doctor_of_Ineptitude:

I don't see the WTF in this. I was expecting a hate filled life threatening coffee disrupting termination mail reply. Instead all I got to see was a professional response.

Actually, the WTF is Phil, whose take-home assignment only measures the candidate's ability to use google.

And yet, somehow, Boris failed even by those anemic standards.

The real WTF is the apparent lack of WTF punchline. I mean, Boris' "homework" answer approaches CodeSOD levels, but it was rejected along with Boris, yielding an uncharacteristically happy ending for everyone except Boris.

WTF?

minimus2012-11-08 12:03

verisimilidude:

if (($Number > 0) AND ($Number < 1))
{
return (FALSE)
}
else
{
return (TRUE)
}

I see his level of expertise right there. If he can't do

return ($Number > 0) AND ($Number < 1)

then his code it too wordy for consideration.

And we see yours...

Daniel2012-11-08 12:05

I was looking at some code I wrote a few years ago and testing for 2, 3, 5 & 7 are sufficient... if your using SPRP (Strong Probable Prime) instead of modulus.

If n < 25,000,000,000 is a 2, 3, 5 and 7-SPRP, then either n = 3,215,031,751 or n is prime. This covers all unsigned 32 bit integers.

% R
> library(gmp)
> isprime(37)
1
> isprime(100)
0

cellocgw2012-11-08 12:07

TRWTF is interviewing Boris instead of Natasha.

lmm2012-11-08 12:10

cellocgw:

TRWTF is interviewing Boris instead of Natasha.

ITYM Nataliya.

cellocgw2012-11-08 12:14

lmm:

cellocgw:

TRWTF is interviewing Boris instead of Natasha.

ITYM Nataliya.

Ya not familiar with Moose and Squirrel?

chubertdev2012-11-08 12:20

DCRoss:

Anonymous:

Take the number 99999997 as an example. Say you only check odd number until you reach number/2. You have now tested about 25 million numbers and you know you found a prime! However, if you use square root as a limit you only need to test about 10000 numbers. Of course you only need to check the odd ones so then you are down to 5000.

If you want to get picky, you only need to check the factors which are prime themselves. As long as you have a fresh supply of interview candidates and undergrad students to provide you with lists of primes that cuts it down further to just over 1000.

The tough part is that you get into recursion checking if the number is prime inside the loop. More efficient to just run the modulus test.

WhiskeyJack2012-11-08 12:31

cellocgw:

TRWTF is interviewing Boris instead of Natasha.

Doris?

Elron the Fantastic2012-11-08 12:32

99999997 is not prime.

1297 * 77101 = 99999997

You sir, fail at prime numbers.

PedanticCurmudgeon2012-11-08 12:37

Not Badinoff:

The real WTF is the apparent lack of WTF punchline. I mean, Boris' "homework" answer approaches CodeSOD levels, but it was rejected along with Boris, yielding an uncharacteristically happy ending for everyone except Boris.

WTF?

But imagine if Boris had enough google skills to find an implementation and copy it. He would have been hired despite his obvious inability to code his way out of a paper bag.

Actually, the real WTF was given by Phil in one of his comments. Phil's colleagues wanted to hire Boris anyway.

Cbuttius2012-11-08 12:43

Elron the Fantastic:

99999997 is not prime.

1297 * 77101 = 99999997

You sir, fail at prime numbers.

I had already pointed that one out at the end of page 1.

C-Derb2012-11-08 12:47

TRWTF was Boris being "eager to gain experience in" PHP.

Elron the Fantastic2012-11-08 12:49

Well, that's what I get for not refreshing the comments page...

Captcha: abico. I abico any responsibility for my failure to properly read all comments.

instigator2012-11-08 13:04

Presentation matters. A bad programmer can still get a job(depending on who's hiring). And, companies without engineering talent can succeed if they have presentation skills (obviously by ripping their customers off).

chubertdev2012-11-08 13:09

Elron the Fantastic:

Well, that's what I get for not refreshing the comments page...

Captcha: abico. I abico any responsibility for my failure to properly read all comments.

This is why, if there are 40+ comments, I wait until there are 50 to add mine. Posts don't exist if they're below the fold.

KattMan2012-11-08 13:42

chubertdev:

Posts don't exist if they're below the fold.

You can fold your monitor?

jay2012-11-08 13:51

When I was in high school, we once had a programming contest where the problem was to write a program that would produce a list of all the prime numbers less than 100. Entries were to be judged based on accuracy, conciseness and efficiency. Namely, any programs that produced incorrect results failed. Working programs were then scored by multiplying the number of lines of code (excluding comments) by the run-time, and low score wins. (Which, by the way, I think is an excellent scoring system.)

A friend of mine submitted a program that looked basically like this (I don't have the original listing, but this was the basic idea):

His entry had the fewest lines of code and the fastest run-time, so under the rules, he should have won. He also commented that he thought the algorithm was very easy to understand and so the program was highly maintainable. But the teachers disqualified him.

jay2012-11-08 14:08

JC:

No, factorizing* prime numbers is what is neigh-on impossible. Determining if any given number is a prime is very much possible.

* "Prime Factorization" is finding which prime numbers multiply together to make the original number.

I can write a function to factor a prime number very easily.

int[] factorsOfPrime(int prime)
{
/* Note: This function assumes that "prime" is, indeed,
a prime number. */
int[] factors=new int[2];
factors[0]=1;
factors[1]=prime;
return factors;
}

Perhaps you meant that factoring a composite number is very difficult? It's certainly not conceptually difficult -- you can always do it with the simple "loop through successive integers attempting to divide" method and when you get a hit, pass the quotient back in to the same function recursively. e.g. say you start with 455. Divide by 2? No. 3? No. 5? Yes, quotient is 91. So first factor is 5. Now repeat process using 91. Divide by 5? (Note we can start with the divisor that last succeeded, as we already know it's not divisible by smaller numbers.) Anyway, divide by 5? No. 7? Yes. Quotient is 13. So add 7 to list of factors. Now work on 13. We start at 7, we're already past the square root, so we're done. 13 is the last factor. Prime factorization is therefore 5*7*13.

Perhaps you meant that finding prime factors of very large composites in some reasonable amount of time is difficult.

jMerliN2012-11-08 14:09

JC:

"Hum, you realize that making an efficient prime number detector for all possible values is currently impossible."

No, factorizing* prime numbers is what is neigh-on impossible. Determining if any given number is a prime is very much possible.

* "Prime Factorization" is finding which prime numbers multiply together to make the original number.

I don't think that's quite right. You see, if it's trivial to determine if a number N is prime, that necessarily means you know at least one factor: 1 < F < N. If this is the case, then recursively apply this test to N/F and you've trivially factored N. But because factoring N is nontrivial, it seems that this wouldn't be possible.

This is similar to the reason why it's impossible to create a general compression algorithm that can compress N bits into N-1 bits without loss. Recursive application necessarily yields a contradiction.

Sam I am2012-11-08 14:21

I am constantly amazed by how many commenters here are unable to conceive of a brute-force algorithm to solve a well-defined problem.

BAD! NO! I know that PHP is TRWTF, but you should at least know why your suggestion is wrong before you make the claim.

A PHP variable, under the hood, is a struct that stores the base type, and the typed representations of the variable for each base type. (Yes, for each of the 6 base types: int, float, string, bool, object, and reference. The WTF is strong with PHP.)

When you test a variable using the == operator, it evaluates the type of the lvalue to find the correctly-typed internal value of the rvalue to compare against the lvalue.

When you test a variable using the === operator, it evaluates the type of the lvalue against the type of the rvalue, and if that matches, it then evaluates the value of the lvalue against the value of the rvalue.

The reason your third checkInteger fails is because it coerces the type of the lvalue. When you cast (int)$num, it's creating a copy of $num, but setting its type to int. Then you're comparing type-for-type against an uncoerced $num. If $num is anything but an int already, this implementation of checkInteger will fail.

A correctly idiot-proofed PHP function should always treat "1" the same as 1. If a PHP-hack-claiming-to-be-a-dev called checkInteger("1"), it should work correctly and return true.

But wait! There's another WTF buried here. Since the (int)$num takes the internal integer representation from $num and makes it the "real" value of that instance of $num, then compares it to the original $num's internal integer instance, this function effectively proves nothing but identity.

Think of PHP variables as a struct:

struct PHPVar {
int typeEnum;
int intVar;
float floatVar;
string stringVar;
bool boolVar;
object objectVar;
int* refVar;
}

If you have one that's set up like so:

PHPVar1 {
typeEnum = 3; // 3 = string, for this exercise
intVar = 1;
floatVar = 1.0;
stringVar = "1";
boolVar = true;
objectVar = null; // because a constant isn't an object
refVar = null; // because a constant isn't a reference either
}

When you cast it to an int, you get this:

PHPVar2 {
typeEnum = 1; // 1 = int, for this exercise
intVar = 1;
floatVar = 1.0;
stringVar = "1";
boolVar = true;
objectVar = null; // because a constant isn't an object
refVar = null; // because a constant isn't a reference either
}

So when you compare PHPVar1->intVar == PHPVar2->intVar, you always get true, regardless of the value of either ones typeEnum.

Repeat after me: PHP is TRWTF.

chubertdev2012-11-08 14:37

KattMan:

chubertdev:

Posts don't exist if they're below the fold.

You can fold your monitor?

Yeah, I'm pretty buff.

foo2012-11-08 15:33

David F. Skoll:

When asked to prove that all odd numbers greather than two are prime:

The mathematician said: "3 is prime, 5 is prime, 7 is prime, ... and so on."

The engineer said: "3 is prime, 5 is prime, 7 is prime, 9 is experimental error, 11 is prime..."

The arts major said: "What does 'prime' mean?"

Boris said: "3 is ... an integer (and prime), 5 is ..... an integer (and prime), 7 is ....... an integer, 9 is ......... an integer. -0.5 is ............................." (and he starved)

foo2012-11-08 15:38

Some Guy:

A PHP variable, under the hood, is a struct that stores the base type, and the typed representations of the variable for each base type. (Yes, for each of the 6 base types: int, float, string, bool, object, and reference. The WTF is strong with PHP.)

You mean every value is converted to 5 other types (99.9% of which conversions are never used)? Please tell me that's not true! I knew PHP was a big WTF, but that beats everything. A great way to waste both memory and runtime simultaneously, and at such a fundamental level.

Ken B2012-11-08 15:41

urza9814:

Remy Porter:

You can make it slightly more efficient by breaking the loop at $val / 2, since you've already divided by 2 by the time you get there.

You can make it FAR more efficient by using the square root. Anything larger than that would have to be multiplied by something smaller than that, which you would have already tested.

And you only need to check for divisible by 2, and then by odd numbers 3 and up. (No need to check for divisibility by even numbers other than 2.)

I did that (mumble, mumble) years ago in junior high school.

Vlad Patryshev2012-11-08 15:41

CCD, Can't Code Disease.

Regarding foreigners and phone interviews, one of my favorite phone questions is "can you write a regex that checks if parentheses are correct in an arithmetic expression?" - and I know the right candidate when they start laughing. Mostly it happens if you call a candidate in Poland; they have an excellent education there.
(Disclaimer: I've never even been to Poland.)

foo2012-11-08 15:47

captcha:augue:

So you got experience with C and embedded systems? Great, you're the perfect candidate for our PHP job!

The other way around would be a much bigger WTF of course, but it's still a waste of a low-level programmer.

Actually, by hiring him and putting him to work on a dummy PHP project that will never see the light of day, they could have done humanity a big favour. Think about it: Now Boris may go on to work on a life-support, traffic-control, airplane, nuclear-safety, etc. system that your life may one day depend on ...

(And no, it's not possible that Boris may just be a great C/embedded programmer. Even though he won't have to checkInteger in C, there's plenty of WTFs in those code samples to make this absolutely certain.)

foo2012-11-08 15:50

Matt:

This smacks of someone who had too much math and not enough sense.

Last time I checked, math included the definition of prime numbers greater than 7.

No, to me it smacks of someone who has much too big an ego (billable code, what?) and not enough clue of anything.

DrPepper2012-11-08 15:51

I had an interview where I had to write a prime number algorithm on a white board, in C#. Didn't do too bad at it, but not too good either. So I felt challenged, and that afternoon I went back to the drawing board.

I wrote a single linq statement that correctly calculated the prime numbers up to some arbitrary number.

var cnt=1000000;

var query = (from two in Enumerable.Range(2,1) select two) .Union (from candidate in Enumerable.Range(3, cnt-2).Where(p => p % 2 != 0) select candidate).AsParallel() .Except ((from candidate in Enumerable.Range(3, cnt-2).Where(p => p % 2 != 0).AsParallel() from q1 in Enumerable.Range(3, (int)Math.Sqrt(candidate)).Where(p => p % 2 != 0).AsParallel() where q1 < candidate && candidate % q1 == 0 select candidate) .Distinct()).OrderBy(x => x);

foreach (int i in query) Console.WriteLine(i);

da Doctah2012-11-08 16:13

Rnd(:

urza9814:

Remy Porter:

You can make it slightly more efficient by breaking the loop at $val / 2, since you've already divided by 2 by the time you get there.

You can make it FAR more efficient by using the square root. Anything larger than that would have to be multiplied by something smaller than that, which you would have already tested.

Test the oddity and start 3 and add increase by 2 each time.

Or am I wrong with this? Should't it about double efficiency?

I'm just a noob though...

(1) Test last digit for even/odd.
(2) Test last digit to determine whether divisible by 5.
(3) Starting with 3, test for divisibility by numbers ending in 3, 7, 9, or 1.

I just knocked about another 20% off your execution time. You're welcome.

Melnorme2012-11-08 16:13

...why is nobody commenting on the fact that checkInteger and checkDouble are _exactly identical_.

Boris was not just an idiot, he was a liar.

Computer Scientist2012-11-08 16:21

An engineer, physicist and Computer Scientist we're asked to show whether all odd numbers were prime.

The engineer (a bit miffed that we was being bothered with such an irrelevant problem) suggested that until someone (not him) could offer a counter example of an odd number that was not prime, we should accept that all odd numbers might be prime.

The physicist chose some odd numbers, 3,5,7,11 and concluded that as all of these were prime, it might be a reasonable hypothesis that all odd numbers should be prime.

The Computer Scientist (possibly Boris) went away and laboured on a a complex algorithm to determine whether a given input was Prime. He tested it extensively before declaring that all odd numbers must be prime:
3....PRIME
3....PRIME
3....PRIME
3....PRIME
3....PRIME
...

Jim2012-11-08 16:28

PedanticCurmudgeon:

Doctor_of_Ineptitude:

I don't see the WTF in this. I was expecting a hate filled life threatening coffee disrupting termination mail reply. Instead all I got to see was a professional response.

Actually, the WTF is Phil, whose take-home assignment only measures the candidate's ability to use google.

Not really. I've given similar assignments to candidates and made it clear to them that I'm happy for them to use any resources available (hell, when I don't know how to do something at work, I use Google).

As a preliminary exercise it filters out some of the useless - and a few questions (at a subsequent interview) about how their solution works and obstacles they found in creating their program usually exposes those who understand what their program does (irrespective of whether they wrote it or copied it) and those who definitely copied it without understanding how it works.
Of those who can explain how it works, it doesn't really bother me whether they made it themselves or copied someone else's directly (the fact they understand the workings is reasonable assurance that they won't blindly copy stuff that doesn't work - and may be more inclined to use in-built API's than the gung-ho developer who believes they can make a good Calendar/Date class).

Do you want a candidate who has a limited amount of skill that will never develop, or one that is happy to teach themselves by googling for ideas?

Jr2012-11-08 16:40

Cbuttius:

And once when I wrote one, I tested if the number was greater than 5. Then tested divisbility only for numbers with mod 30 that were:

1, 7, 11, 13, 17, 19, 23, 29

so only 8 numbers out of every 30.

Incidentally I have my own formula for calcuating if numbers are prime, which I usually use for 4 digit numbers and it involves performing modulo arithmetic by certain numbers, then resolving as a difference of two squares. If the number can be resolved as such a way it is not prime, if it cannot then it is.

Example number 4769. We normally test divisibility first by 2, 3, 5, 7, 11 and 13. You can go a bit further with the normal method. In any case it is clear that the number is not divisible by 2, 3 or 5. With regards to the next 3 we can reduce with the 1001 rule, so we reduce to 765 which we can quickly deduce is not divisible by any of those 3.

Now we look at the modulo arithmetic of the number.

- 8 mod 9. That means it would be the difference of a number divisible by 9 and one whose square is 1 mod 9. In any case we normally look at the upper number in the difference, so we are looking for a number divisible by 3.

- 1 mod 8. So the upper number must be odd.

- 4 mod 5. Upper number may be divisible by 5, otherwise we can go further and say its 12 or 13 mod 25. Quite a reduction.

- 2 mod 7. Squares mod 7 are 0, 1, 2, 4 so the number must square to a 2 or a 4. That means it cannot be divisible by 7 or 1 or -1 mod 7.

Looking at the square root of the number we have, it's above 69.

The first number that passes all our tests is 75, then 87, then there are none until 135.

5625-4769 is 856 which isn't square. The square root of this value is around 29 so we can already say we've resolved all possibly prime factors up to 41.

87 squared is 8100-540+9 = 7569. Subtract 4769 and you get 2800 which isn't square either. Now we've got a bit further though, sqrt(2800) is approximately 53 so solved up to 34. Ok not much progress, only ruled out 37.

However our next effort is 135:

135 squared is 18225. Subtract 4769 is 13456, and we can actually work out this is 116 squared... So we've found the solution, 4769 is divisible by 19 (multiplied by 251, the sum of 135 and 116).

The real WTF is working out Primes on the fly like that for each Prime.

You use these sort of algorithms to create look-up tables. If you need to find whether a number beyond your list is prime, you can always extend it (using the same formula).

Startup:
calculate primes to 19
Eg: Test if 9 is Prime - Lookup.
Test if 25 is prime - better extend list to 29 and lookup
Test if 23 is prime - lookup
test if 34 is prime - extend list to 37 and lookup
etc....

of course if it's a one off (or a trivial case (%2) then it might be overkill) - but in the real world nothing is ever a one-off.

Jack 272012-11-08 16:45

But the candidate failed, so score one for that assignment.

I'd say "ability to use google" is necessary but not sufficient for most programming jobs.

Anyway, you could use this assignment also to check coding and documentation style, unless they just copy it directly from the internet (which you should be able to discover if you also know how to use google).

eric762012-11-08 16:45

Rodnas:

Before you star developers are all going to show us minor gods how it is done... i did what any sane programmer would do and searched the internet for an answer.

All i found was inefficient code. Well it is better than no code at all

If there was efficient code to do it, then any encryption based on the product of two large prime numbers would be easy to break.

Muck2012-11-08 16:48

Mark:

Phil:

What's missing from the story is that after my response to his second submission, he asked if the work would be billable; that was when we asked him (nicely) to please go away.

Ah, Boris was actually demonstrating his ability to do consulting in the real world. On the 3rd or 4th time upgrading this function, after much time billed and wasted, he would then give you something that worked. I bet Boris went far.

Do consultants actually give something that works eventually, or are you just saying that so we keep giving you another bite at the cherry?

jason2012-11-08 16:50

of course you only check the prime numbers <= sqrt

Julie2012-11-08 16:56

Anoldhacker:

Phil:

If I remember correctly, the algorithm in Applied Cryptography is a fast way of getting what is probably the right answer as long as you can stand a few false negatives (so it might tell you that your prime number isn't prime but not vice versa). I could be wrong, it's a long time ago and I have never had to look at it since.

So, you check if Fermat's Little Theorem holds for the possible prime with a few candidates. If not, it fails. If so, then it starts to look like it might be prime.... http://en.wikipedia.org/wiki/Primality_test

In crypto, you are usually just looking for SOME prime number, not a definite statement about a particular number. In that case, a false negative usually not a problem.

In GENERATING crypto you are just looking for a Prime.
In BREAKING Crypto you are looking for a prime which (coupled with another prime) gets you some number....of course (as someone else said) the issue is in being able to FACTORIZE the number - the primeness of the components is only important in so far as it narrows down the field to test from - but if the effort to determine primeness exceeds the saving, then you might as well just try to divide by every number, ignoring whether it's prime or not - you're kind of guaranteed that the result will be prime...

Simplified EG:
need to factorize: 35
Work out primes:
2 (known)
3%2=1 => 3
4%2 =0 no good
5%2, 5%3 != 0 => good
Test 35/2 no good. 35/3 no good. 35/5 - winner winner, chicken dinner

Alternative;y, forget primes....
35/2 no good
35/3 no good
35/4 no good
35/5 Winner, Winner, chicken dinner.

Maybe (sometimes) working out if a number is prime is overkill

Mikey2012-11-08 17:09

hikari:

neminem:

For the job I'm at, I had a similar experience - after the usual silly discussion questions, they gave me a couple really small programming questions, that I think I did a decent job of. Then they asked me a larger one - convert an int to its roman numeral expansion (or possibly the reverse, I forget, it was a while ago). That is the sort of problem domain I would not have had any reason to be an expert in before being asked to solve it, and my first response in a real scenario would clearly be visiting wikipedia for what the full rules of roman numerals even were. I had to ask a bunch of questions. So they said just go home, write it and email it. Interview ended at around 5 PM, I had it to them by 8 the next morning. It definitely would not have been nearly such a nice experience if I'd had to do the whole thing writing on a whiteboard with no internet.

Giving a whole week seems needlessly nice, though.

Roman numerals give you fun problems anyway. There's never been a formal way of writing them; clocks, for example, tend to use IIII for 4, whereas people will tend to write it as IV.

Clocks use Roman Numerals? Well I'll be darned....

AFAIK most pedants consider IIII more correct (as in that's what Julius Scissors would have used), but the convention these days is IV.

Whoa2012-11-08 17:10

Tim:

Well obviously he should have called out to a web service using XML. There must be one somewhere that can tell you if a given number is prime.

Just hope it isn't encrypted over https. Because in setting up the crypto you'll probably need some prime numbers! Recursion lurks wherever you look. If you don't see it at first, look closer.

The whole world is a fractal?

I'm off for some Almond Bread.

Mikey2012-11-08 17:12

Caesar:

hikari:

Roman numerals give you fun problems anyway. There's never been a formal way of writing them; clocks, for example, tend to use IIII for 4, whereas people will tend to write it as IV.

Roman numerals were invented by people who had to chisel them in stone. There's no way you'd chop away at "IIII" when you could simply do "IV".

On the other hand we think about reuse....

If we're counting the number of times something happens, it's useful to be able to reuse I when making II, then III then IIII.
Otherwise we have to chuck our rock out quickly.

This is particularly true when keeping score in gladitorial sports (how many gladiators has this dude killed already). I guess it's kind of feasible that it was rare for someone to kill more than 3 before they get snuffed....

Caesar2012-11-08 17:50

Mikey:

Caesar:

hikari:

Roman numerals give you fun problems anyway. There's never been a formal way of writing them; clocks, for example, tend to use IIII for 4, whereas people will tend to write it as IV.

Roman numerals were invented by people who had to chisel them in stone. There's no way you'd chop away at "IIII" when you could simply do "IV".

On the other hand we think about reuse....

If we're counting the number of times something happens, it's useful to be able to reuse I when making II, then III then IIII.
Otherwise we have to chuck our rock out quickly.

This is particularly true when keeping score in gladitorial sports (how many gladiators has this dude killed already). I guess it's kind of feasible that it was rare for someone to kill more than 3 before they get snuffed....

Don't be ridiculous! You count gladiator victories by throwing another stick on the pile. Chiseling in stone is for constants, not variables.

havokk2012-11-08 18:27

Caesar:

Roman numerals were invented by people who had to chisel them in stone. There's no way you'd chop away at "IIII" when you could simply do "IV".

As far as I understand it, roman numerals were invented by people carving notches into tally sticks. They are an ordinal representation. Carving 9 notches into the tally stick gives IIIIVIIII, which is then abreviated to VIIII (since a V implies four Is before it). Carving 19 notches is IIIIVIIIIXIIIIVIIII, abbreviated to XVIIII (since X implies IIIIVIIII before it).

Bill C.2012-11-08 18:45

TRWTF is how did the prime candidate ever graduate from electoral college?

And that test of integrity, that should be illegal.

Anon2012-11-08 19:01

What I found interesting about this article was that I had written up two of my own prime-testing programs, one a brute force checker (from 1 to sqrt(number)) and one that only checked a list of already found prime numbers, and added to the list if the number was found prime. I was quite proud of the last one, giving it the ability to "learn" what numbers needed to be checked, but it ended up taking ~45 times longer than the brute force method(2050 seconds, about 34 minutes, as compared to 45 seconds for the brute-force check) to calculate what numbers up to 1,000,000 were prime.

Oh Well.

(note: I'm not a professional (read: I'm a complete amateur) writing in Java))

hikari2012-11-08 19:17

Mikey:

Caesar:

hikari:

Roman numerals give you fun problems anyway. There's never been a formal way of writing them; clocks, for example, tend to use IIII for 4, whereas people will tend to write it as IV.

Roman numerals were invented by people who had to chisel them in stone. There's no way you'd chop away at "IIII" when you could simply do "IV".

On the other hand we think about reuse....

If we're counting the number of times something happens, it's useful to be able to reuse I when making II, then III then IIII.
Otherwise we have to chuck our rock out quickly.

This is particularly true when keeping score in gladitorial sports (how many gladiators has this dude killed already). I guess it's kind of feasible that it was rare for someone to kill more than 3 before they get snuffed....

For things of a transitory nature Romans used wax tablets. For things that needed to be permanently recorded, they wrote them down on papyrus, parchment, or vellum. Romans highly respected and prized the ability to write.

Anon2012-11-08 19:18

Anon:

What I found interesting about this article was that I had written up two of my own prime-testing programs, one a brute force checker (from 1 to sqrt(number)) and one that only checked a list of already found prime numbers, and added to the list if the number was found prime. I was quite proud of the last one, giving it the ability to "learn" what numbers needed to be checked, but it ended up taking ~45 times longer than the brute force method(2050 seconds, about 34 minutes, as compared to 45 seconds for the brute-force check) to calculate what numbers up to 1,000,000 were prime.

Oh Well.

(note: I'm not a professional (read: I'm a complete amateur) writing in Java))

Not 10 seconds after I hit "submit" I realised a way to drastically reduce the amount of time required for the second method. It now takes just under 3 times as long (174073 milliseconds as opposed to 62551 milliseconds. And yes I'm using real-time clocks, as I didn't need any big-O notation to realise it used to be crazy innefficient).

herby2012-11-08 19:25

jay:

When I was in high school, we once had a programming contest where the problem was to write a program that would produce a list of all the prime numbers less than 100. Entries were to be judged based on accuracy, conciseness and efficiency. Namely, any programs that produced incorrect results failed. Working programs were then scored by multiplying the number of lines of code (excluding comments) by the run-time, and low score wins. (Which, by the way, I think is an excellent scoring system.)

A friend of mine submitted a program that looked basically like this (I don't have the original listing, but this was the basic idea):

His entry had the fewest lines of code and the fastest run-time, so under the rules, he should have won. He also commented that he thought the algorithm was very easy to understand and so the program was highly maintainable. But the teachers disqualified him.

Many years ago, there were always students posting to various language groups on usenet. On comp.lang.c this problem came up quite often in the beginning of the school year. While the number of primes was usually those less than 1000, the given answer was always the same for the "can you give me a program" question. Yes, just a bunch of print statements with the numbers included.

Most likely the student realized:
1) Yes, the answer WAS correct as it did print the correct numbers.
2) The answer was likely to get a failing grade since it did now show an algorithm.
3) A little research was in order (before Google!).

This falls into the category of answering questions with the word "or" in them with "yes" (eg: Are you male or female?).

Kerin2012-11-08 19:26

PedanticCurmudgeon:

So TRWTF was left out of the article entirely. How typical.

Hey, don't knock it. Obfuscated WTFs are way more fun to figure out. :)

Matthew2012-11-08 19:37

Wrong
Factorization is what RSA depends on, which is hard. Testing if a number is a prime fast is solved

http://en.wikipedia.org/wiki/AKS_primality_test

(in fact RSA relies on being able to test for primes very fast in order to select the two primes the key is made from)

jMerliN2012-11-08 19:57

Matthew:

Wrong
Factorization is what RSA depends on, which is hard. Testing if a number is a prime fast is solved

http://en.wikipedia.org/wiki/AKS_primality_test

(in fact RSA relies on being able to test for primes very fast in order to select the two primes the key is made from)

It blows my mind that you can determine that a number is prime without knowing any of its factors. I need to brush up on my number theory.

I'm almost just as surprised that JRebel has found a pig large enough so that a single strip of bacon from it can completely encircle a Ferrari.

Man, everything is impressive today.

Harrow2012-11-08 21:48

No wonder he was nervous...

-Harrow.

Jim2012-11-08 22:18

Matthew:

Wrong
Factorization is what RSA depends on, which is hard. Testing if a number is a prime fast is solved

http://en.wikipedia.org/wiki/AKS_primality_test

(in fact RSA relies on being able to test for primes very fast in order to select the two primes the key is made from)

Well...IMHO (which is probably worth less than all you cleveries out there) the problem is that the security of RSA relies on the unpredictability of primes. Once primes are shown to follow a pattern (which as I understand it is one of the corollaries to the Japanese Mathematician's paper) then RSA becomes considerably less secure, because we suddenly have a quick way to verify the factorization that we are doing is really involving primes...

That said, IIRC (and it's a long time since I did anything involving RSA - and only ever in a school environment) the RSA problem is about taking two primes p,q and then multiplying (p-1)*(q-1) rather than pq (pq is used, but I don't think known). What this means is that the problem is not quite as straight forward as factoring into primes....
eg:
p=7, q=11
(p-1)*(q-1) = 6*10 = 60 (2,3,4,5,6,10,12,15,20,30) all divide that. Of course, it's still rather advantageous to be able to know which numbers are prime, so that we can test prime-1.....

And I could be totally wrong....I'm no mathamagician.

Coyne2012-11-09 00:49

Anonymous:

Take the number 99999997 as an example. Say you only check odd number until you reach number/2. You have now tested about 25 million numbers and you know you found a prime! However, if you use square root as a limit you only need to test about 10000 numbers. Of course you only need to check the odd ones so then you are down to 5000.

Another simple hack can cut it to by another third to 2667 numbers: Alternately increment by 2 and 4, starting with 5. That not only skips evens, but also numbers divisible by 3.

Addendum (2012-11-09 01:00): Oh, and alternating the inc: inc = 6-inc

Steve The Cynic2012-11-09 03:50

jMerliN:

It blows my mind that you can determine that a number is prime without knowing any of its factors. I need to brush up on my number theory.

If N is a prime, I (by definition) know all its factors: 1 and N. A prime has no other factors but 1 and itself. Go back and check your sources again...

Cbuttius2012-11-09 04:41

My "difference of squares" rule is what I use to calculate if numbers are prime in my head. With regards to mental arithmetic, I find squaring fairly simple and working out if a number is square fairly simple too.

Of course if you were using a computer program to do this you would be able to store a table of squares.

That mine had 19 as the first prime factor made it perhaps less efficient for this particular formula. It is generally more efficient when the number actually is prime, and when the prime factors are higher.

Take as another example 2773. Yes, I picked this number on purpose this time.

You go through your early checks but when you see the square root is just under 53, and work out that 53 is a valid "top" number to try for it, you will immediately arrive at the fact that 53 squared is 2809 which is 36 more than the target number, which means 2773 is 47 * 59.

Addendum (2012-11-09 04:49):

2773 is 5 mod 8, 1 mod 9, 3 mod 5, 1 mod 7. We're looking for numbers that are odd, 1 or 8 mod 9, 2 or 3 mod 5 and 1, 3, 4 or 6 mod 7.

53 satisfies all of those. Note the mod 9 rule eliminates more than any of the others here. 73 would have been the next eligible target, followed by 127.

plasmab2012-11-09 04:46

Meh,

This is pretty typical of what I expect from developers really. Mainly ignorant and egotistical.

There are very few good developers.

chris2012-11-09 05:00

verisimilidude:

if (($Number > 0) AND ($Number < 1))
{
return (FALSE)
}
else
{
return (TRUE)
}

I see his level of expertise right there. If he can't do

return ($Number > 0) AND ($Number < 1)

then his code it too wordy for consideration.

A lot of less-experienced devs seem to have a blind spot for the fact that you can put a boolean calculation directly into a return statement or a function argument, even if the same people have no trouble writing "return a * b + c" for a numeric type.

Can you still blame BASIC for this nowadays? :-)

JimLahey2012-11-09 05:33

I was going to say something along those lines. Judging by his efforts he should be writing best practice guidelines for www.php.net

erat2012-11-09 06:03

Mike:

So judge the code, not the algorithm.

Only if the code is good should you even consider looking at if the algorithm is good.

Dammit! All my code contains algorithms!

ASheridan2012-11-09 08:45

chubertdev:

below the fold.

This is TRWTF. The fold is for print, not for web. Anyone who says otherwise is stupid and/or delusional.

Chris P. Peterson2012-11-09 09:38

Primes is in P jackass. Look it up.

gnasher7292012-11-09 09:46

StupidTheKid:

Hum, you realize that making an efficient prime number detector for all possible values is currently impossible. The difficulty of finding prime numbers is what makes RSA secure after all...

Wrong. What makes RSA secure is the difficulty of finding the factors of the product of two large primes. If it was hard to find large primes, then RSA wouldn't work at all, because you need to find two large random primes to create the keys.

Chris2012-11-09 09:58

ASheridan:

chubertdev:

below the fold.

This is TRWTF. The fold is for print, not for web. Anyone who says otherwise is stupid and/or delusional.

Actually, TRWTF is not realizing that words sometimes morph over time to encompass very different meanings than what they originally were for. Especially when used in a slightly different industry.

Just one simple example: Bolt http://dictionary.reference.com/browse/bolt?s=t

ASheridan2012-11-09 10:14

Chris:

Actually, TRWTF is not realizing that words sometimes morph over time to encompass very different meanings than what they originally were for. Especially when used in a slightly different industry.

I realise that the word is being used to mean something else, but it's really not applicable. The fold doesn't exist on a screen where a huge mix of resolutions means you can't ever know where it is. So sure, morph the word all you want, it's still wrong.

chubertdev2012-11-09 11:54

ASheridan:

Chris:

Actually, TRWTF is not realizing that words sometimes morph over time to encompass very different meanings than what they originally were for. Especially when used in a slightly different industry.

I realise that the word is being used to mean something else, but it's really not applicable. The fold doesn't exist on a screen where a huge mix of resolutions means you can't ever know where it is. So sure, morph the word all you want, it's still wrong.

What word would you use? Google is failing me when it comes to finding a better one.

ASheridan2012-11-09 12:37

chubertdev:

What word would you use? Google is failing me when it comes to finding a better one.

I wouldn't use any word because the very concept is faulty. It only came about because print designers were treating the web like print, which it isn't and never will be.

jay2012-11-09 13:49

da Doctah:

(1) Test last digit for even/odd.
(2) Test last digit to determine whether divisible by 5.
(3) Starting with 3, test for divisibility by numbers ending in 3, 7, 9, or 1.

I just knocked about another 20% off your execution time. You're welcome.

Nice try, but no.

Is it faster for the computer to extract the last digit and then test that for even/odd or divisible by 5, rather than testing the number as a whole? How are you going to extract the last digit? If you say, "Convert the number to a decimal string, then convert the string to a character array, then examine the last digit", big time fail. That would require multiple divisions by 10, creating new objects, etc etc. No ways that's going to be faster than just dividing by 2. Even if you think a little harder and say, okay, all we need to do to get the last digit is to take the number mod 10 ... well, how is

lastdigit = number mod 10
if lastdigit mod 2 = 0 then ...

going to be faster than

if number mod 2 = 0 then ...

You're doing two mods instead of one. I don't see how that helps.

Similarly, "only try numbers that end in 3, 7, 9, or 1". How do you find those numbers? You seem to think that

lastdigit = x mod 10
if lastdigit mod 2 = 0 then return false
if lastdigit mod 5 = 0 then return false
for n = 3 to sqrt(x)
lastdigit = n mod 10
if lastdigit = 3
or lastdigit = 7
or lastdigit = 9
or lastdigit = 1 then
if x mod n = 0 then return false
return true

will be faster than

for n = 2 to sqrt(x) step 2
if x mod n = 0 then return false
return true

Moving two of the tests outside of the loop does nothing for run time. You still have to do the compares. No performance gain there. Plus it takes more code.

As to the rest, do you really think that doing 2 mods and 5 compares is faster than 1 mod and 1 compare? Why would that be true?

The lesson to be learned here is: Just because a shortcut works for a human being looking at decimal representations doesn't mean that it will be helpful for a computer looking at binary.

David2012-11-09 14:18

ASheridan:

chubertdev:

What word would you use? Google is failing me when it comes to finding a better one.

I wouldn't use any word because the very concept is faulty. It only came about because print designers were treating the web like print, which it isn't and never will be.

And furthermore, no concept from the print industry can or ever will be a valid analogy for a similar concept on the web?

That being the case, what word would you use for web content that is not immediately visible (ie without scrolling) after page load?

Not because the concept of "page load" has any meaning whatsoever in the print industry, obviously. Just curious.

Kasper2012-11-09 14:26

MightyM:

Remy Porter:

You can make it slightly more efficient by breaking the loop at $val / 2, since you've already divided by 2 by the time you get there.

Actually you only need to iterate to the squareroot of $val.

And you don't have to compute the square root in order to do that. You can just square $i and compare to $val. Additionally you can check divisibility by two outside of the loop and only check odd numbers in the loop. I think this is the fastest you can do before it starts getting complicated:

The part about skipping even numbers can be generalized. But by the time you generalize that, you no longer need equal steps between the candidates for your divisor, and then it starts getting complicated.

Skipping even numbers is simple and saves you 1/2 of the execution time. Skipping numbers divisible by three only saves 1/3 of the remaining execution time. The payoff decreases with every prime you avoid this way, and complexity increases.

If you for example consider the primes up to 7, you get a cycle of length 210 of which you have to test 48 of them. You can precompute such a cycle of what length you prefer. I think by the time the length of the cycle would exceed the square root of the largest candidate to consider it no longer pays off. That means the length of the cycle needs to be less than the square root of the square root of the number. If the numbers are 64 bits, you'd reach the limit already when you have multiplied 2, 3, 5, 7, 11, and 13. Multiplying by 17 as well would give you a number which is larger than sqr(sqr(2^64)). I don't think the theoretical 16% savings from including 11 and 13 would be enough for me to bother implementing this algorithm.

chubertdev2012-11-09 15:06

ASheridan:

chubertdev:

What word would you use? Google is failing me when it comes to finding a better one.

I wouldn't use any word because the very concept is faulty. It only came about because print designers were treating the web like print, which it isn't and never will be.

If the concept is faulty, why does it work in practice? Comments at bottom of a page are simply not read as often as comments at the top of a page.

Boris2012-11-10 16:53

This is a prime comment http://thedailywtf.com/Comments/AddComment.aspx?ArticleId=7437

k2012-11-11 04:12

I was under the impression that factorizing prime numbers is exceedingly simple.

katastrofa2012-11-11 08:50

Brent:

Remy Porter:

If someone gave me this "homework", the first thing I'd ask would be, "Do you just want a naive implementation, or should I use a more efficient algorithm? If you want the simple approach, I could rip that out right now."

That's a very important thing to do. I have a friend that when asked to do the Fibonacci Sequence, proceeded to quickly work out the closed form expression and coded that. This confused the interviewers to no end.

The closed form implementation is not equivalent in practice to the recursive implementation. Did your friend know that?

katastrofa2012-11-11 08:51

k:

I was under the impression that factorizing prime numbers is exceedingly simple.

Yes, if you know they're prime.

Coyne2012-11-11 18:01

Some Guy:

A PHP variable, under the hood, is a struct that stores the base type, and the typed representations of the variable for each base type. (Yes, for each of the 6 base types: int, float, string, bool, object, and reference. The WTF is strong with PHP.)

When you test a variable using the == operator, it evaluates the type of the lvalue to find the correctly-typed internal value of the rvalue to compare against the lvalue.

When you test a variable using the === operator, it evaluates the type of the lvalue against the type of the rvalue, and if that matches, it then evaluates the value of the lvalue against the value of the rvalue.

The reason your third checkInteger fails is because it coerces the type of the lvalue. When you cast (int)$num, it's creating a copy of $num, but setting its type to int. Then you're comparing type-for-type against an uncoerced $num. If $num is anything but an int already, this implementation of checkInteger will fail.

A correctly idiot-proofed PHP function should always treat "1" the same as 1. If a PHP-hack-claiming-to-be-a-dev called checkInteger("1"), it should work correctly and return true.

But wait! There's another WTF buried here. Since the (int)$num takes the internal integer representation from $num and makes it the "real" value of that instance of $num, then compares it to the original $num's internal integer instance, this function effectively proves nothing but identity.

Think of PHP variables as a struct:

struct PHPVar {
int typeEnum;
int intVar;
float floatVar;
string stringVar;
bool boolVar;
object objectVar;
int* refVar;
}

[---snip---]

Oversimplified just a bit. Yes, a PHP variable is a struct, but one member of the struct is a union (the item called "value", here).

Casting can't work that way exactly, because if you change the type, the content of "value" would also have to change, since these variables are overlaid and not separate primitives.

So if the types of two elements of an "==" compare are not of the same type then a cast would have to occur (explicit) or implicit and so your example at the end would happen more like this:

PHPVar1 {
union {
lval = 1; // integer value
dval; // doesn't exist str; // doesn't exist *Ht; // doesn't exist obj; // doesn't exist }
type = 'l'; // string type
}

So a cast can't simply just change the type; it also has to set the correct member of the union, in order to ensure that the structure is correct for the new type.

I've done a little PHP, and I'm not sure it is a WTF in whole (though it certainly contains it's fair share of RWTF's, which isn't surprising given its history).

ASheridan2012-11-12 04:14

What content is that? Is that content viewed on a laptop screen, a large widescreen, a TV, a standard circa 90s 4:3 monitor? Just giving that unknown quantity of hidden content a name that means something different in the print industry does not make the issue of not knowing how much content is actually shown/hidden go away.

ASheridan2012-11-12 04:33

chubertdev:

If the concept is faulty, why does it work in practice? Comments at bottom of a page are simply not read as often as comments at the top of a page.

Nice strawman, but what you're saying is actually two different things. Things towards the top of the page are generally more important. But that has nothing to do with a "fold". In the past 3 years I've tracked over 550 different screen resolutions, and of those there's nearly 400 different heights for screen resolutions. Now tell me that there is a fold and that you know where it is.

Cbuttius2012-11-12 11:49

If your target number is 1 mod 4 then you can also test if it is the sum of two squares.

If it is not the sum of two squares it is definitely NOT prime. However if it is, that is not a proof that it is prime.

e.g.

13, 17, 29, 37 and 41 are all the sum of two squares, but 21 and 33 are not.

(13=4+9, 17=1+16, 29=4+25, 37=1+36, 41=16+25)

25 is itself square as well as being 9+16 and 45 is 9+36, so as I said, being the sum of two squares is not a proof of primeness, but failing to be such is a clear test of non-primeness.

Assuming you have a table of squares less than your number you can thus eliminate some numbers without any divisions at all.

Note that if the number is 3 mod 4 it will never be the sum of two primes.

chubertdev2012-11-12 12:17

ASheridan:

chubertdev:

If the concept is faulty, why does it work in practice? Comments at bottom of a page are simply not read as often as comments at the top of a page.

Nice strawman, but what you're saying is actually two different things. Things towards the top of the page are generally more important. But that has nothing to do with a "fold". In the past 3 years I've tracked over 550 different screen resolutions, and of those there's nearly 400 different heights for screen resolutions. Now tell me that there is a fold and that you know where it is.

A comment is more important just because it happens to be #52 instead of #48? :headscratch:

ASheridan2012-11-12 12:41

chubertdev:

A comment is more important just because it happens to be #52 instead of #48? :headscratch:

Now you're just being deliberately stupid.

Paul Neumann2012-11-12 14:28

chubertdev:

ASheridan:

chubertdev:

If the concept is faulty, why does it work in practice? Comments at bottom of a page are simply not read as often as comments at the top of a page.

Nice strawman, but what you're saying is actually two different things. Things towards the top of the page are generally more important. But that has nothing to do with a "fold". In the past 3 years I've tracked over 550 different screen resolutions, and of those there's nearly 400 different heights for screen resolutions. Now tell me that there is a fold and that you know where it is.

A comment is more important just because it happens to be #52 instead of #48? :headscratch:

I'll "fold"... Where do I go to change the count for comment pagination on this site?

dont hire me2012-11-12 16:15

Fast naive solution in python

def is_prime(n):
return n >= 2 and all(map(lambda d: n % d, range(2, int(n ** 0.5) + 1)))

def primes(n):
i = 2
while i < n:
if is_prime(i):
yield i
i += 1

Decius2012-11-13 15:00

JC:

"Hum, you realize that making an efficient prime number detector for all possible values is currently impossible."

No, factorizing* prime numbers is what is neigh-on impossible. Determining if any given number is a prime is very much possible.

* "Prime Factorization" is finding which prime numbers multiply together to make the original number.

Factoring can be done trivially in time equal to the square root of the number to be factored. The factors are efficient, it's just that numbers can be arbitrarily large.

Neil2012-11-14 08:12

Matt:

This smacks of someone who had too much math and not enough sense. The "beauty" of integers is that you can define an almost-infinite sequence of them recursively with only the postulates of "one" and "plus". So, naturally, that's how he tested whether the input was a member of the set of integers.

Better still, use "zero" and "increment". I won't bother linking to the Peano postulates for obvious reasons, akismet.

Vlad Patryshev:

Regarding foreigners and phone interviews, one of my favorite phone questions is "can you write a regex that checks if parentheses are correct in an arithmetic expression?" - and I know the right candidate when they start laughing. Mostly it happens if you call a candidate in Poland; they have an excellent education there.
(Disclaimer: I've never even been to Poland.)

That would be due to their experience with Reverse Polish notation.

Mikey:

Clocks use Roman Numerals? Well I'll be darned....

AFAIK most pedants consider IIII more correct (as in that's what Julius Scissors would have used), but the convention these days is IV.

Although clocks use IIII for four, they still prefer IX for nine.

Bill C.:

TRWTF is how did the prime candidate ever graduate from electoral college?

And that test of integrity, that should be illegal.

Well we got to test the prime candidate's integrity at least.

Fernando2012-11-14 10:37

Phil:

My submission included both implementations with an explanation of each including a reference to Applied Cryptography which I thought would impress them (it turned out the interviewer hadn't heard of Bruce Schneier despite being in the crypto field, wtf!)

Does anyone know what algorithm Phil's talking about?
(not that I doubt him, I'm just curious)

Bill C.2012-11-14 19:22

Neil:

Bill C.:

TRWTF is how did the prime candidate ever graduate from electoral college?

And that test of integrity, that should be illegal.

Well we got to test the prime candidate's integrity at least.

Yes, but that's the slippery edge of a fall into a very slippery hole. One thing leads to another and you find yourself testing the integrity of a president. That's why it should be illegal.

Jerome2012-11-15 08:29

I don't know if it's too late t comment on this...

But as a general rule, for me, if someone shows up for an interview and seems extremely nervous/edgy/fidgety, I assume they are high. (From personal experience. I am a recovering addict.)

In my case it was meth, but anybody coming across like that could be high on meth, coke or crack.

When he asked to be excused, that would have ended the interview immediately. (Don't want junkies taking hits in our company toilet, thank you very much.)

Norman Diamond2012-11-15 19:51

Jerome:

I don't know if it's too late t comment on this...

Not too late, and I hope it's not too late for you to learn something from this.

Jerome:

But as a general rule, for me, if someone shows up for an interview and seems extremely nervous/edgy/fidgety, I assume they are high. (From personal experience. I am a recovering addict.)

Some of us are better at programming than at telling good stories for interviews, so we get nervous/edgy/fidgety when we are not high. Unless you count the caffeine for which we drink tea, coffee, cola, etc.

Jerome:

When he asked to be excused, that would have ended the interview immediately. (Don't want junkies taking hits in our company toilet, thank you very much.)

One of my heart medicines is a diuretic. You would end the interview not because of my heart issue but because of your prejudicial assumption. You're not alone; WTF bosses are half of this site.

SomeGuy2012-12-03 21:46

Norman Diamond:

One of my heart medicines is a diuretic. You would end the interview not because of my heart issue but because of your prejudicial assumption. You're not alone; WTF bosses are half of this site.

You're old and have a bad heart? Well, you're eliminated (no pun intended...though unintentional puns are sometimes better) anyway due to other prejudices.

rlyle11792012-12-11 13:25

Phil:

Anyway, Boris failed miserably but I wanted to have a rock solid case against hiring him as others in the company were keen to get him in regardless so that's why I gave him a second chance. What's missing from the story is that after my response to his second submission, he asked if the work would be billable; that was when we asked him (nicely) to please go away.

I find it's a better policy not to hire anyone if anybody raises a red flag on the candidate. As our result, our engineering team is rock solid.

AlexH2012-12-13 20:54

Is it just me, or does Boris's "checkInteger" go into an infinite recursion when $Number is -0.5?

Rachel2013-01-12 18:16

"Yeah, I'm pretty duff."

FTFY! ;)

Teagan422013-08-08 12:19

Please tell me this is sarcasm...

if not, then you need to realize that he is only checking if the number is evenly divisible by 2, 3, 5, and 7 - if it's not then it's PRIME. Given that 121 is not divisible by 2, 3, 5 or 7 his program would return "PRIME" but 121 is COMPOSITE (11 * 11 = 121)

Heck, how did people like Boris kept themselves from starving back then?

1. They don't use google and produce bad code. Fail.

2. They don't use google but manage to produce (potentially weak) code that solves the problem. Pass.

3. They use google and still produce bad code. Fail.

4. They use google and come up with a good solution. Pass.

You can then test them further if you want to, but it gives a good baseline of their ability to solve a problem. They either know the subject area already, or research it to find the solution. Either way, if they solve the problem with good code then they are on the right path.

Except by whichever place maintains phpMyAdmin. Boris would definitely raise standards there.

You are right! That will be a massive problem when you hire him and he's not allowed an internet connection!

Actually you only need to iterate to the squareroot of $val.

You can make it FAR more efficient by using the square root. Anything larger than that would have to be multiplied by something smaller than that, which you would have already tested.

All i found was inefficient code. Well it is better than no code at all

And by slightly, we mean REALLY slightly. The classic first improvement is to stop at sqrt($val). It starts to get more interesting after that.

Test the oddity and start 3 and add increase by 2 each time.

Or am I wrong with this? Should't it about double efficiency?

I'm just a noob though...

The real WTF is that the programming exercise was not the first step. There were probably many candidates who were rejected at the CV stage who would have passed that test easily.

Because that one is too obvious?

Still, PHP instead of C... Doctored CV?

1, 7, 11, 13, 17, 19, 23, 29

so only 8 numbers out of every 30.

Incidentally I have my own formula for calcuating if numbers are prime, which I usually use for 4 digit numbers and it involves performing modulo arithmetic by certain numbers, then resolving as a difference of two squares. If the number can be resolved as such a way it is not prime, if it cannot then it is.

Example number 4769. We normally test divisibility first by 2, 3, 5, 7, 11 and 13. You can go a bit further with the normal method. In any case it is clear that the number is not divisible by 2, 3 or 5. With regards to the next 3 we can reduce with the 1001 rule, so we reduce to 765 which we can quickly deduce is not divisible by any of those 3.

Now we look at the modulo arithmetic of the number.

- 8 mod 9. That means it would be the difference of a number divisible by 9 and one whose square is 1 mod 9. In any case we normally look at the upper number in the difference, so we are looking for a number divisible by 3.

- 1 mod 8. So the upper number must be odd.

- 4 mod 5. Upper number may be divisible by 5, otherwise we can go further and say its 12 or 13 mod 25. Quite a reduction.

- 2 mod 7. Squares mod 7 are 0, 1, 2, 4 so the number must square to a 2 or a 4. That means it cannot be divisible by 7 or 1 or -1 mod 7.

Looking at the square root of the number we have, it's above 69.

The first number that passes all our tests is 75, then 87, then there are none until 135.

5625-4769 is 856 which isn't square. The square root of this value is around 29 so we can already say we've resolved all possibly prime factors up to 41.

87 squared is 8100-540+9 = 7569. Subtract 4769 and you get 2800 which isn't square either. Now we've got a bit further though, sqrt(2800) is approximately 53 so solved up to 34. Ok not much progress, only ruled out 37.

However our next effort is 135:

135 squared is 18225. Subtract 4769 is 13456, and we can actually work out this is 116 squared... So we've found the solution, 4769 is divisible by 19 (multiplied by 251, the sum of 135 and 116).

I actually had drawn on my own prior experience of a telephone interview where my prospective employer was in a different country. I was quite inexperienced and didn't have much to show as sample code so they asked me to submit an implementation of a test for primeness. I thought this was quite a good assignment as there is an easy solution (sieve of Eratosthenes) and then various more complex but efficient solutions.

In my case, I got an implementation of "sieve" working quite quickly and then got to work on another algorithm from Applied Cryptography (I don't remember the name). My submission included both implementations with an explanation of each including a reference to Applied Cryptography which I thought would impress them (it turned out the interviewer hadn't heard of Bruce Schneier despite being in the crypto field, wtf!)

In the end, they didn't offer me the job but I thought I'd keep it in mind as a good programming assignment to test if someone is:

1. capable of implementing a basic algorithm

2. inclined to do a bit of research (googling) to see if there is something better out there

Anyway, Boris failed miserably but I wanted to have a rock solid case against hiring him as others in the company were keen to get him in regardless so that's why I gave him a second chance. What's missing from the story is that after my response to his second submission, he asked if the work would be billable; that was when we asked him (nicely) to please go away.

http://www.scientificamerican.com/article.cfm?id=proof-claimed-for-deep-connection-between-prime-numbers

No, factorizing* prime numbers is what is neigh-on impossible. Determining if any given number is a prime is very much possible.

* "Prime Factorization" is finding which prime numbers multiply together to make the original number.

Using square root of the number as a limit makes a big difference when the prime candidates starts to grow.

Take the number 99999997 as an example. Say you only check odd number until you reach number/2. You have now tested about 25 million numbers and you know you found a prime! However, if you use square root as a limit you only need to test about 10000 numbers. Of course you only need to check the odd ones so then you are down to 5000.

Yeah, I was about to say that just his checkInteger() function should have been more than enough to disqualify him as it is possibly the least efficient way of calculating it. Even if you ignore native PHP methods for determining type (is_int() comes to mind), you could write an integer checker much more simply by just doing this:

or

or

or

...

I, too, was recently given the prime number test during an interview. Well the last time I did that was 32 years ago in Fortran. And I usually don't write code on a whiteboard with someone watching me. I'll stub out the structure (loops etc.) then go back and fill in the details.

So, anyway, I didn't get the job. Never mind that I could have helped them secure their website, and the guy they hired apparently can't, because it is still penetrable. At least he could rattle off an algorithm during an interview.

He could have HALVED the amount of code just by using PHP's is_int() function.

That's enough of a reason to stop reading and fail his test right there.

Pretty much meant further optimisation. There is a why more tricks I think, but at some point it's better to move to some more specialised algorithms.

Anyway anyone got prime test which uses no extra memory or minimal amount of it?

Any post-launch issues can be dealt with by the bug fixers. We could probably even charge extra for the performance upgrade.

}

else

{

Now if I could only figured out what he hoped to accomplish with:

"

\n");

Ah, Boris was actually demonstrating his ability to do consulting in the real world. On the 3rd or 4th time upgrading this function, after much time billed and wasted, he would then give you something that worked. I bet Boris went far.

To do the latter, build a prime number table.

To build a prime number table up to N, mark every cell with itself. You can of course make the table size N-1 as we don't test 0 or 1 for primeness.

Take the first prime number which is 2. You now mark every product of 2 with the number 2. Next is 3: You know this is prime because it's still marked with a 3. You jump to its square and mark every 3rd number that currently has itself as the value with a 3.

4 is marked as non-prime so continue with 5.

Once we get to a value where the square is beyond N we stop and we have our prime number table. Then constant time to check if a number it contains is prime or not.

If we want to check the primeness of a number beyond the table, we at least know what the primes are so we know what values to try modding it by, so more efficient in those numbers too.

So, you check if Fermat's Little Theorem holds for the possible prime with a few candidates. If not, it fails. If so, then it starts to look like it might be prime.... http://en.wikipedia.org/wiki/Primality_test

In crypto, you are usually just looking for SOME prime number, not a definite statement about a particular number. In that case, a false negative usually not a problem.

Bear in mind that the candidate proclaimed to have little or no knowledge of PHP, and was only using that language to expand his programming abilities; a very commendable effort in and of itself.

Not to mention, this was 2000; PHP 4 (which first included is_int() and is_numeric()) was released only halfway through that year, so he may have well used PHP 3.

Last but not least: those of us working with PHP for a long time know that the language can do pretty much anything for you, natively. But people used to languages like C start of with the assumption that by default your language has about two tools, and everything else needs to be loaded from libraries. After a while, a PHP's programmer first instinct when faced with a new problem will be to search if there is a default function available to do that, but it takes time before that mindset is achieved.

That's a very important thing to do. I have a friend that when asked to do the Fibonacci Sequence, proceeded to quickly work out the closed form expression and coded that. This confused the interviewers to no end.

I got to code some C so I obfuscate my comments ;D Just use preprocessor to remove why ;D

Giving a whole week seems needlessly nice, though.

I think I would have just gone and looked up an algorithm on-line or in one of my books - one of them is bound to have one in - and then implemented it.

I have a similar reaction to interviews as the candidate in the story; I end up talking in a muted whisper, sweating, and shaking. Sometimes in life I get lucky and interview with people who can see through this (like my current employers). Having people who are willing to make effort to interview people like us makes me really rather appreciative.

If you want to get picky, you only need to check the factors which are prime themselves. As long as you have a fresh supply of interview candidates and undergrad students to provide you with lists of primes that cuts it down further to just over 1000.

Or I might get as far as 1297 and discover that it is not prime. (1297 * 77101)

The other way around would be a much bigger WTF of course, but it's still a waste of a low-level programmer.

Roman numerals give you fun problems anyway. There's never been a formal way of writing them; clocks, for example, tend to use IIII for 4, whereas people will tend to write it as IV.

Just hope it isn't encrypted over https. Because in setting up the crypto you'll probably need some prime numbers! Recursion lurks wherever you look. If you don't see it at first, look closer.

The mathematician said: "3 is prime, 5 is prime, 7 is prime, ... and so on."

The engineer said: "3 is prime, 5 is prime, 7 is prime, 9 is experimental error, 11 is prime..."

The arts major said: "What does 'prime' mean?"

Yes, which is why I write all my algorithms to accept input in "Simplified Roman Numerals"-- None of this "VXLCM" nonsense, just give me "IIIIIIIIIIII" for 12.

It also has the benefit of making those pesky NP-hard problems run in polynomial time (of the length of the input)

--Joe

No, factorising *prime* numbers is very easy ... by definition, the sole factor is the number itself. It's factorising large NON-prime numbers that gets tricky, and that's the bit that's needed for breaking public-key crypto systems like RSA.

Done?

It doesn't really matter if the prime test is correct. This is an interview to see if the guy can code. So judge the code, not the algorithm. There is plenty of evidence in the first sample (which worked for a small set of numbers) that the coding is sloppy and misguided.

Only if the code is good should you even consider looking at if the algorithm is good.

My other thought was, even if they guy's code was great, would you hire him after such a bad interview? If his code was great, and you turned him down, you could be in a whole lot of bother if he challenged the decision any the grounds of any form of discrimination he chooses as your only hard evidence is a good piece of code!

{

return (FALSE)

}

else

{

return (TRUE)

}

I see his level of expertise right there. If he can't do

return ($Number > 0) AND ($Number < 1)

then his code it too wordy for consideration.

Said the horse.

And yet, somehow, Boris failed even by those anemic standards.

The real WTF is the apparent lack of WTF punchline. I mean, Boris' "homework" answer approaches CodeSOD levels, but it was rejected along with Boris, yielding an uncharacteristically happy ending for everyone except Boris.

WTF?

And we see yours...

If n < 25,000,000,000 is a 2, 3, 5 and 7-SPRP, then either n = 3,215,031,751 or n is prime. This covers all unsigned 32 bit integers.

int Prime (unsigned n)

{

if (n == 3215031751)

return FALSE;

if (n <= 10)

{

return (n == 2) || (n == 3) || (n == 5) || (n == 7);

}

if ((n % 2) == 0)

return FALSE;

return b_SPRP (n,2) && b_SPRP (n,3) &&

b_SPRP (n,5) && b_SPRP (n,7);

}

Sources:

http://primes.utm.edu/prove/prove2_3.html

http://www.olivierlanglois.net/archive/prime_cpp.htm

And yes, I am the Daniel fixed a bug in the second link.

Way too long.

% R

> library(gmp)

> isprime(37)

1

> isprime(100)

0

ITYM Nataliya.

Ya not familiar with Moose and Squirrel?

The tough part is that you get into recursion checking if the number is prime inside the loop. More efficient to just run the modulus test.

Doris?

1297 * 77101 = 99999997

You sir, fail at prime numbers.

Actually, the real WTF was given by Phil in one of his comments. Phil's colleagues wanted to hire Boris anyway.

I had already pointed that one out at the end of page 1.

Captcha: abico. I abico any responsibility for my failure to properly read all comments.

This is why, if there are 40+ comments, I wait until there are 50 to add mine. Posts don't exist if they're below the fold.

You can fold your monitor?

A friend of mine submitted a program that looked basically like this (I don't have the original listing, but this was the basic idea):

10 PRINT "2,3,5,7,11,13,17,19,23,29,31,37,41,43,47"

20 PRINT "53,59,61,67,71,73,79,83,89,97"

His entry had the fewest lines of code and the fastest run-time, so under the rules, he should have won. He also commented that he thought the algorithm was very easy to understand and so the program was highly maintainable. But the teachers disqualified him.

I can write a function to factor a prime number very easily.

Perhaps you meant that factoring a composite number is very difficult? It's certainly not conceptually difficult -- you can always do it with the simple "loop through successive integers attempting to divide" method and when you get a hit, pass the quotient back in to the same function recursively. e.g. say you start with 455. Divide by 2? No. 3? No. 5? Yes, quotient is 91. So first factor is 5. Now repeat process using 91. Divide by 5? (Note we can start with the divisor that last succeeded, as we already know it's not divisible by smaller numbers.) Anyway, divide by 5? No. 7? Yes. Quotient is 13. So add 7 to list of factors. Now work on 13. We start at 7, we're already past the square root, so we're done. 13 is the last factor. Prime factorization is therefore 5*7*13.

Perhaps you meant that finding prime factors of very large composites in some reasonable amount of time is difficult.

I don't think that's quite right. You see, if it's trivial to determine if a number N is prime, that necessarily means you know at least one factor: 1 < F < N. If this is the case, then recursively apply this test to N/F and you've trivially factored N. But because factoring N is nontrivial, it seems that this wouldn't be possible.

This is similar to the reason why it's impossible to create a general compression algorithm that can compress N bits into N-1 bits without loss. Recursive application necessarily yields a contradiction.

BAD! NO! I know that PHP is TRWTF, but you should at least know why your suggestion is wrong before you make the claim.

A PHP variable, under the hood, is a struct that stores the base type, and the typed representations of the variable for each base type. (Yes, for each of the 6 base types: int, float, string, bool, object, and reference. The WTF is strong with PHP.)

When you test a variable using the == operator, it evaluates the type of the lvalue to find the correctly-typed internal value of the rvalue to compare against the lvalue.

When you test a variable using the === operator, it evaluates the type of the lvalue against the type of the rvalue, and if that matches, it then evaluates the value of the lvalue against the value of the rvalue.

The reason your third checkInteger fails is because it coerces the type of the lvalue. When you cast (int)$num, it's creating a copy of $num, but setting its type to int. Then you're comparing type-for-type against an uncoerced $num. If $num is anything but an int already, this implementation of checkInteger will fail.

A correctly idiot-proofed PHP function should always treat "1" the same as 1. If a PHP-hack-claiming-to-be-a-dev called checkInteger("1"), it should work correctly and return true.

But wait! There's another WTF buried here. Since the (int)$num takes the internal integer representation from $num and makes it the "real" value of that instance of $num, then compares it to the original $num's internal integer instance, this function effectively proves nothing but identity.

Think of PHP variables as a struct:

If you have one that's set up like so:

When you cast it to an int, you get this:

So when you compare PHPVar1->intVar == PHPVar2->intVar, you always get true, regardless of the value of either ones typeEnum.

Repeat after me: PHP is TRWTF.

Yeah, I'm pretty buff.

I did that (mumble, mumble) years ago in junior high school.

Regarding foreigners and phone interviews, one of my favorite phone questions is "can you write a regex that checks if parentheses are correct in an arithmetic expression?" - and I know the right candidate when they start laughing. Mostly it happens if you call a candidate in Poland; they have an excellent education there.

(Disclaimer: I've never even been to Poland.)

(And no, it's not possible that Boris may just be a great C/embedded programmer. Even though he won't have to checkInteger in C, there's plenty of WTFs in those code samples to make this absolutely certain.)

No, to me it smacks of someone who has much too big an ego (billable code, what?) and not enough clue of anything.

I wrote a single linq statement that correctly calculated the prime numbers up to some arbitrary number.

var cnt=1000000;

var query = (from two in Enumerable.Range(2,1) select two) .Union (from candidate in Enumerable.Range(3, cnt-2).Where(p => p % 2 != 0) select candidate).AsParallel() .Except ((from candidate in Enumerable.Range(3, cnt-2).Where(p => p % 2 != 0).AsParallel() from q1 in Enumerable.Range(3, (int)Math.Sqrt(candidate)).Where(p => p % 2 != 0).AsParallel() where q1 < candidate && candidate % q1 == 0 select candidate) .Distinct()).OrderBy(x => x);

foreach (int i in query) Console.WriteLine(i);

(1) Test last digit for even/odd.

(2) Test last digit to determine whether divisible by 5.

(3) Starting with 3, test for divisibility by numbers ending in 3, 7, 9, or 1.

I just knocked about another 20% off your execution time. You're welcome.

Boris was not just an idiot, he was a liar.

The engineer (a bit miffed that we was being bothered with such an irrelevant problem) suggested that until someone (not him) could offer a counter example of an odd number that was not prime, we should accept that all odd numbers might be prime.

The physicist chose some odd numbers, 3,5,7,11 and concluded that as all of these were prime, it might be a reasonable hypothesis that all odd numbers should be prime.

The Computer Scientist (possibly Boris) went away and laboured on a a complex algorithm to determine whether a given input was Prime. He tested it extensively before declaring that all odd numbers must be prime:

3....PRIME

3....PRIME

3....PRIME

3....PRIME

3....PRIME

...

Not really. I've given similar assignments to candidates and made it clear to them that I'm happy for them to use any resources available (hell, when I don't know how to do something at work, I use Google).

As a preliminary exercise it filters out some of the useless - and a few questions (at a subsequent interview) about how their solution works and obstacles they found in creating their program usually exposes those who understand what their program does (irrespective of whether they wrote it or copied it) and those who definitely copied it without understanding how it works.

Of those who can explain how it works, it doesn't really bother me whether they made it themselves or copied someone else's directly (the fact they understand the workings is reasonable assurance that they won't blindly copy stuff that doesn't work - and may be more inclined to use in-built API's than the gung-ho developer who believes they can make a good Calendar/Date class).

Do you want a candidate who has a limited amount of skill that will never develop, or one that is happy to teach themselves by googling for ideas?

The real WTF is working out Primes on the fly like that for each Prime.

You use these sort of algorithms to create look-up tables. If you need to find whether a number beyond your list is prime, you can always extend it (using the same formula).

Startup:

calculate primes to 19

Eg: Test if 9 is Prime - Lookup.

Test if 25 is prime - better extend list to 29 and lookup

Test if 23 is prime - lookup

test if 34 is prime - extend list to 37 and lookup

etc....

of course if it's a one off (or a trivial case (%2) then it might be overkill) - but in the real world nothing is ever a one-off.

I'd say "ability to use google" is necessary but not sufficient for most programming jobs.

Anyway, you could use this assignment also to check coding and documentation style, unless they just copy it directly from the internet (which you should be able to discover if you also know how to use google).

If there was efficient code to do it, then any encryption based on the product of two large prime numbers would be easy to break.

GENERATINGcrypto you are just looking for a Prime.In

BREAKINGCrypto you are looking for a prime which (coupled with another prime) gets you some number....of course (as someone else said) the issue is in being able to FACTORIZE the number - the primeness of the components is only important in so far as it narrows down the field to test from - but if the effort to determine primeness exceeds the saving, then you might as well just try to divide by every number, ignoring whether it's prime or not - you're kind of guaranteed that the result will be prime...Simplified EG:

need to factorize: 35

Work out primes:

2 (known)

3%2=1 => 3

4%2 =0 no good

5%2, 5%3 != 0 => good

Test 35/2 no good. 35/3 no good. 35/5 - winner winner, chicken dinner

Alternative;y, forget primes....

35/2 no good

35/3 no good

35/4 no good

35/5 Winner, Winner, chicken dinner.

Maybe (sometimes) working out if a number is prime is overkill

AFAIK most pedants consider IIII more correct (as in that's what Julius Scissors would have used), but the convention these days is IV.

I'm off for some Almond Bread.

If we're counting the number of times something happens, it's useful to be able to reuse I when making II, then III then IIII.

Otherwise we have to chuck our rock out quickly.

This is particularly true when keeping score in gladitorial sports (how many gladiators has this dude killed already). I guess it's kind of feasible that it was rare for someone to kill more than 3 before they get snuffed....

As far as I understand it, roman numerals were invented by people carving notches into tally sticks. They are an ordinal representation. Carving 9 notches into the tally stick gives IIIIVIIII, which is then abreviated to VIIII (since a V implies four Is before it). Carving 19 notches is IIIIVIIIIXIIIIVIIII, abbreviated to XVIIII (since X implies IIIIVIIII before it).

And that test of integrity, that should be illegal.

What I found interesting about this article was that I had written up two of my own prime-testing programs, one a brute force checker (from 1 to sqrt(number)) and one that only checked a list of already found prime numbers, and added to the list if the number was found prime. I was quite proud of the last one, giving it the ability to "learn" what numbers needed to be checked, but it ended up taking ~45 times longer than the brute force method(2050 seconds, about 34 minutes, as compared to 45 seconds for the brute-force check) to calculate what numbers up to 1,000,000 were prime.

Oh Well.

(note: I'm not a professional (read: I'm a complete amateur) writing in Java))

For things of a transitory nature Romans used wax tablets. For things that needed to be permanently recorded, they wrote them down on papyrus, parchment, or vellum. Romans highly respected and prized the ability to write.

Not 10 seconds after I hit "submit" I realised a way to drastically reduce the amount of time required for the second method. It now takes just under 3 times as long (174073 milliseconds as opposed to 62551 milliseconds. And yes I'm using real-time clocks, as I didn't need any big-O notation to realise it used to be crazy innefficient).

Many years ago, there were always students posting to various language groups on usenet. On comp.lang.c this problem came up quite often in the beginning of the school year. While the number of primes was usually those less than 1000, the given answer was always the same for the "can you give me a program" question. Yes, just a bunch of print statements with the numbers included.

Most likely the student realized:

1) Yes, the answer WAS correct as it did print the correct numbers.

2) The answer was likely to get a failing grade since it did now show an algorithm.

3) A little research was in order (before Google!).

This falls into the category of answering questions with the word "or" in them with "yes" (eg: Are you male or female?).

Hey, don't knock it. Obfuscated WTFs are way more fun to figure out. :)

Factorization is what RSA depends on, which is hard. Testing if a number is a prime fast is solved

http://en.wikipedia.org/wiki/AKS_primality_test

(in fact RSA relies on being able to test for primes very fast in order to select the two primes the key is made from)

It blows my mind that you can determine that a number is prime without knowing any of its factors. I need to brush up on my number theory.

I'm almost just as surprised that JRebel has found a pig large enough so that a single strip of bacon from it can completely encircle a Ferrari.

Man, everything is impressive today.

-Harrow.

That said, IIRC (and it's a long time since I did anything involving RSA - and only ever in a school environment) the RSA problem is about taking two primes p,q and then multiplying (p-1)*(q-1) rather than pq (pq is used, but I don't think known). What this means is that the problem is not quite as straight forward as factoring into primes....

eg:

p=7, q=11

(p-1)*(q-1) = 6*10 = 60 (2,3,4,5,6,10,12,15,20,30) all divide that. Of course, it's still rather advantageous to be able to know which numbers are prime, so that we can test prime-1.....

And I could be totally wrong....I'm no mathamagician.

Another simple hack can cut it to by another third to 2667 numbers: Alternately increment by 2 and 4, starting with 5. That not only skips evens, but also numbers divisible by 3.

Addendum (2012-11-09 01:00):Oh, and alternating the inc: inc = 6-inc

If N is a prime, I (by definition) know all its factors: 1 and N. A prime has no other factors but 1 and itself. Go back and check your sources again...

Of course if you were using a computer program to do this you would be able to store a table of squares.

That mine had 19 as the first prime factor made it perhaps less efficient for this particular formula. It is generally more efficient when the number actually is prime, and when the prime factors are higher.

Take as another example 2773. Yes, I picked this number on purpose this time.

You go through your early checks but when you see the square root is just under 53, and work out that 53 is a valid "top" number to try for it, you will immediately arrive at the fact that 53 squared is 2809 which is 36 more than the target number, which means 2773 is 47 * 59.

Addendum (2012-11-09 04:49):2773 is 5 mod 8, 1 mod 9, 3 mod 5, 1 mod 7. We're looking for numbers that are odd, 1 or 8 mod 9, 2 or 3 mod 5 and 1, 3, 4 or 6 mod 7.

53 satisfies all of those. Note the mod 9 rule eliminates more than any of the others here. 73 would have been the next eligible target, followed by 127.

This is pretty typical of what I expect from developers really. Mainly ignorant and egotistical.

There are very few good developers.

A lot of less-experienced devs seem to have a blind spot for the fact that you can put a boolean calculation directly into a return statement or a function argument, even if the same people have no trouble writing "return a * b + c" for a numeric type.

Can you still blame BASIC for this nowadays? :-)

Dammit! All my code contains algorithms!

This is TRWTF. The fold is for print, not for web. Anyone who says otherwise is stupid and/or delusional.

Wrong. What makes RSA secure is the difficulty of finding the factors of the product of two large primes. If it was hard to find large primes, then RSA wouldn't work at all, because you need to find two large random primes to create the keys.

Actually, TRWTF is not realizing that words sometimes morph over time to encompass very different meanings than what they originally were for. Especially when used in a slightly different industry.

Just one simple example: Bolt http://dictionary.reference.com/browse/bolt?s=t

I realise that the word is being used to mean something else, but it's really not applicable. The fold doesn't exist on a screen where a huge mix of resolutions means you can't ever know where it is. So sure, morph the word all you want, it's still wrong.

What word would you use? Google is failing me when it comes to finding a better one.

I wouldn't use any word because the very concept is faulty. It only came about because print designers were treating the web like print, which it isn't and never will be.

Nice try, but no.

Is it faster for the computer to extract the last digit and then test that for even/odd or divisible by 5, rather than testing the number as a whole? How are you going to extract the last digit? If you say, "Convert the number to a decimal string, then convert the string to a character array, then examine the last digit", big time fail. That would require multiple divisions by 10, creating new objects, etc etc. No ways that's going to be faster than just dividing by 2. Even if you think a little harder and say, okay, all we need to do to get the last digit is to take the number mod 10 ... well, how is

going to be faster than

You're doing two mods instead of one. I don't see how that helps.

Similarly, "only try numbers that end in 3, 7, 9, or 1". How do you find those numbers? You seem to think that

will be faster than

Moving two of the tests outside of the loop does nothing for run time. You still have to do the compares. No performance gain there. Plus it takes more code.

As to the rest, do you really think that doing 2 mods and 5 compares is faster than 1 mod and 1 compare? Why would that be true?

The lesson to be learned here is: Just because a shortcut works for a human being looking at decimal representations doesn't mean that it will be helpful for a computer looking at binary.

And furthermore, no concept from the print industry can or ever will be a valid analogy for a similar concept on the web?

That being the case, what word would you use for web content that is not immediately visible (ie without scrolling) after page load?

Not because the concept of "page load" has any meaning whatsoever in the print industry, obviously. Just curious.

Skipping even numbers is simple and saves you 1/2 of the execution time. Skipping numbers divisible by three only saves 1/3 of the remaining execution time. The payoff decreases with every prime you avoid this way, and complexity increases.

If you for example consider the primes up to 7, you get a cycle of length 210 of which you have to test 48 of them. You can precompute such a cycle of what length you prefer. I think by the time the length of the cycle would exceed the square root of the largest candidate to consider it no longer pays off. That means the length of the cycle needs to be less than the square root of the square root of the number. If the numbers are 64 bits, you'd reach the limit already when you have multiplied 2, 3, 5, 7, 11, and 13. Multiplying by 17 as well would give you a number which is larger than sqr(sqr(2^64)). I don't think the theoretical 16% savings from including 11 and 13 would be enough for me to bother implementing this algorithm.

If the concept is faulty, why does it work in practice? Comments at bottom of a page are simply not read as often as comments at the top of a page.

The closed form implementation is not equivalent in practice to the recursive implementation. Did your friend know that?

Yes, if you know they're prime.

Oversimplified just a bit. Yes, a PHP variable is a struct, but one member of the struct is a union (the item called "value", here).

Casting can't work that way exactly, because if you change the type, the content of "value" would also have to change, since these variables are overlaid and not separate primitives.

So if the types of two elements of an "==" compare are not of the same type then a cast would have to occur (explicit) or implicit and so your example at the end would happen more like this:

If you have one that's set up like so:

When you cast it to an int, you get this:

So a cast can't simply just change the type; it also has to set the correct member of the union, in order to ensure that the structure is correct for the new type.

I've done a little PHP, and I'm not sure it is a WTF in whole (though it certainly contains it's fair share of RWTF's, which isn't surprising given its history).

Nice strawman, but what you're saying is actually two different things. Things towards the top of the page are generally more important. But that has nothing to do with a "fold". In the past 3 years I've tracked over 550 different screen resolutions, and of those there's nearly 400 different heights for screen resolutions. Now tell me that there is a fold and that you know where it is.

If it is not the sum of two squares it is definitely NOT prime. However if it is, that is not a proof that it is prime.

e.g.

13, 17, 29, 37 and 41 are all the sum of two squares, but 21 and 33 are not.

(13=4+9, 17=1+16, 29=4+25, 37=1+36, 41=16+25)

25 is itself square as well as being 9+16 and 45 is 9+36, so as I said, being the sum of two squares is not a proof of primeness, but failing to be such is a clear test of non-primeness.

Assuming you have a table of squares less than your number you can thus eliminate some numbers without any divisions at all.

Note that if the number is 3 mod 4 it will never be the sum of two primes.

A comment is more important just because it happens to be #52 instead of #48? :headscratch:

def is_prime(n):

return n >= 2 and all(map(lambda d: n % d, range(2, int(n ** 0.5) + 1)))

def primes(n):

i = 2

while i < n:

if is_prime(i):

yield i

i += 1

Factoring can be done trivially in time equal to the square root of the number to be factored. The factors are efficient, it's just that numbers can be arbitrarily large.

Does anyone know what algorithm Phil's talking about?

(not that I doubt him, I'm just curious)

But as a general rule, for me, if someone shows up for an interview and seems extremely nervous/edgy/fidgety, I assume they are high. (From personal experience. I am a recovering addict.)

In my case it was meth, but anybody coming across like that could be high on meth, coke or crack.

When he asked to be excused, that would have ended the interview immediately. (Don't want junkies taking hits in our company toilet, thank you very much.)

Some of us are better at programming than at telling good stories for interviews, so we get nervous/edgy/fidgety when we are not high. Unless you count the caffeine for which we drink tea, coffee, cola, etc.

One of my heart medicines is a diuretic. You would end the interview not because of my heart issue but because of your prejudicial assumption. You're not alone; WTF bosses are half of this site.

You're old and have a bad heart? Well, you're eliminated (no pun intended...though unintentional puns are sometimes better) anyway due to other prejudices.

I find it's a better policy not to hire anyone if anybody raises a red flag on the candidate. As our result, our engineering team is rock solid.

FTFY! ;)

if not, then you need to realize that he is only checking if the number is evenly divisible by 2, 3, 5, and 7 - if it's not then it's PRIME. Given that 121 is not divisible by 2, 3, 5 or 7 his program would return "PRIME" but 121 is COMPOSITE (11 * 11 = 121)