Suppose we don't know the most efficient algorithm to check if a number is prime or not and we are being asked with this question in an interview. How can we solve this problem?
Based on the definition of prime number, we can simply do this(i ignore the special case when $n === 2 or $n === 1):
function isPrime($n)
{
for($i=2; $i<$n; $i++) {
if($n % $i === 0) {
return false;
}
}
return true;
}
Obviously, this is not efficient, but at least we can solve the problem and give the correct result. I think this is the first step to problem analysis and solving.
Now, we can try to optimize the function. Let's suppose $n is not a prime number, which means it can be divided by two numbers other than 1 and itself. So we have $n = $x * $y. We can find out we definitely should have $x >= 2, and we can have $n / 2 >= $y. So we can change our function:
function isPrime($n)
{
$end = $n / 2;
for($i=2; $i<=$end; $i++) {
if($n % $i === 0) {
return false;
}
}
return true;
}
Cool, it is obviously more efficient than the first one. Now, let's see if we can improve a bit more. Think of $n = $x * $y again. We obviously can have $x >= $y(or $y >= $x, it doesn't matter). So we can have $n >= $y ^ 2. We can change our function again:
function isPrime($n)
{
$end = sqrt($n);
for($i=2; $i<=$end; $i++) {
if($n % $i === 0) {
return false;
}
}
return true;
}
I think this answer could be enough for those who just want to see if you can analyze and solve a problem logically instead of testing your math knowledge.
No comments:
Post a Comment