4 ms·
Why would anyone ask to find primes? Most people don't know the best algorithm and anyone who needs to code efficient ways of determining primality has intense
by hedgie 16y ago
Why would anyone ask to find primes? Most people don't know the best algorithm and anyone who needs to code efficient ways of determining primality has intense number theory training.
The "naive" solution typically is a sieve method and checks more than the required number of factors (goes beyond sqrt(n)). It's like asking someone to sort an array and expecting bubble sort because you never use sorting algorithms in what you actually code.
The best way I know (and there are actually better) to find primes is using an approximation algorithm that no one would ever come up with independently without months of research. The Miller-Rabin primality test finds if a candidate for primality n has a % chance of being prime by looking for numbers a < n that don't satisfy Fermat's little equation. Almost every composite number violates Fermat's little equation (Carmichael numbers are the only exceptions).
Once you hit the desired probability that n is prime (testing more a < n raises this probability) you use a deterministic method to determine 100% if n is prime. If it isn't you throw it out and use Miller-Rabin to find another candidate. Even though you might throw some candidates out and have to pick others to check for primality this method is far faster than a purely deterministic solution using a naive sieve methods.
This is a moronic test of ability. It exposes the arrogance of the company in assuming they can evaluate candidates in 15 minutes by asking the most challenging number theory problems out there when they have no understanding of the current methods in the discipline.
- prodigal_erik 16y agoThe goal is not to illustrate the best algorithm known to researchers, but simply to demonstrate that the candidate can explain the obvious algorithm and get reasonably close to correctly implementing it. Primes is an easy problem to explain and to solve (the naive way), but I wouldn't ask such a commonplace problem because a sub-par candidate may have faced it before and partly memorized the answer.
- hedgie 16y agoIt's not the best algorithm known to researchers. It's the best algorithm known to people who took any course in number theory or a higher level computer science course that covered approximation algorithms. This is used in actual applications like crypto (RSA) frequently. It is exactly like asking an applicant to sort an array and expecting the naive bubble sort response to check they can develop and implement a naive algorithm for searching. It says you can brute force a solution with a for loop. It says nothing about how well you understand advanced data structures, recursion, algorithmic analysis, language features, domain specific knowledge, program design and structure, or knowing when you you're out of your league and should google the best approach. It quizzes chapter 3 of any intro programming book and basic division in a situation where you would never use it. Ask them about event handling or something useful like hash tables or linked lists or version control systems. Any math major can answer this question easily without knowing much beyond for loops and arrays. It tells you almost nothing about their programming skills. I was math/cs with grad school in math and every math major I know could do this. Most of them have no idea how to code. I know some great developers who would struggle and fail because they typically don't use this math in their job and have forgotten it. They work at some of the top companies out there (which are frequently discussed on this webpage).