Idea from http://montreal.pm.org/tech/neil_kandalgaonkar.shtml. Notice that the number cannot be too big.
-
-
Save tsaniel/1098962 to your computer and use it in GitHub Desktop.
function( | |
a // the number | |
){ | |
return !/^,?$|^(,,+)\1+$/.test( | |
Array( // repeat the string ',' | |
-~a // coerce to integer | |
) | |
) | |
} |
function(a){return!/^,?$|^(,,+)\1+$/.test(Array(-~a))} |
DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE | |
Version 2, December 2004 | |
Copyright (C) 2011 YOUR_NAME_HERE <YOUR_URL_HERE> | |
Everyone is permitted to copy and distribute verbatim or modified | |
copies of this license document, and changing it is allowed as long | |
as the name is changed. | |
DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE | |
TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION | |
0. You just DO WHAT THE FUCK YOU WANT TO. |
{ | |
"name": "isPrimeNumber", | |
"description": "Check if a number is prime with RegExp", | |
"keywords": [ | |
"isPrimeNumber", | |
"RegExp", | |
"Prime" | |
] | |
} |
<!DOCTYPE html> | |
<title>isPrimeNumber</title> | |
<div>Expected value: <b>true</b></div> | |
<div>Actual value: <b id="ret"></b></div> | |
<script> | |
var myFunction = function(a){return!/^,?$|^(,,+)\1+$/.test(Array(-~a))}; | |
document.getElementById( "ret" ).innerHTML = myFunction(541) | |
</script> |
Yes, it's an Opera bug or limitation (I think it stops executing the regular expression because of some kind of stack overflow and simply returns false). But it can be avoided. Same behavior in Opera 12 alpha (Win32).
Good catch, @maettig!
In this case, both ungreedy and greedy matching work, the only difference is the ungreedy is faster. (And i think the result of opera is really weird)
@tsaniel, as I said I did a benchmark in both Opera and Firefox. I did not see a difference in runtime.
Picture tells the truth.
http://k.minus.com/jbhrppwzDSzX9N.png
Nice, thanks. Unfortunately the picture is a bit misleading. Ungreedy matching is also very expensive since it requires a look-ahead in each step. These look-aheads are not mentioned in the picture. Plain greedy matching is faster in the first place but may lead to backtracking after the matching is done. That's the problem: You never know if and how many backtracking it causes. On the other side, ungreedy matching is constantly slower. This is why I expected ,+?
to be slower.
However, in the case discussed here it seems both approaches require the same time.
I got an interesting result, the result is different in different browsers, but generally the non-greedy is a little bit faster ;)
Not statistical significant. In average, it's the same. In my revision of the test it's exactly the same. I'm testing all numbers (in this case up to 100) instead of two selected ones. I think this makes the test more realistic.
According to the picture, i think the difference is obvious only if testing big numbers.
Same test with big numbers. Both greedy and ungreedy versions are so slow compared to other solutions, it collapses to an invisible bar in the chart. But you are right, for very large numbers the greedy version is a little bit slower. All solutions (even @p01's) have an exponential complexity of O(d^n) while d is a little bit higher for the greedy regular expression. Update: Mistake in my benchmark. All are almost linear.
Just because these solutions use the brute-force method.
All solutions have an exponential complexity of O(d^n)
I'd like to see a prove for that.
OK, guys. stop wasting your time now and get sane. An End to Negativity!
This actually seems to be an error in the RegExp engine of opera...