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.
isPrimeNumber (using RegExp)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| function( | |
| a // the number | |
| ){ | |
| return !/^,?$|^(,,+)\1+$/.test( | |
| Array( // repeat the string ',' | |
| -~a // coerce to integer | |
| ) | |
| ) | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| function(a){return!/^,?$|^(,,+)\1+$/.test(Array(-~a))} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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. |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| { | |
| "name": "isPrimeNumber", | |
| "description": "Check if a number is prime with RegExp", | |
| "keywords": [ | |
| "isPrimeNumber", | |
| "RegExp", | |
| "Prime" | |
| ] | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <!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> |
Thanks @atk.But it will fail when the input is a string like '541'.
I didn't know ambigious input formats were part of the requirements.
Ah, they are not indeed. But we can use just 2 bytes to get the support of them.
You can reduce (0|a)+1 to -~a. Save more bytes by omitting the 1 and instead count commas.
Down to 55 bytes( 42 if you use Firefox only syntax):
function(a){return!/^,?$|^(,,+?)\1+$/.test(Array(-~a))}
@Kambfhase, you amaze me again. Coercion at it's finest!
You guyz always amaze me :)
I found a confusing behavior. Your 55 bytes version fails for many numbers in the Opera web browser, e.g. for 493 or 529 (all aren't prime numbers). Changing ,+? to ,+ fixes this behavior and saves 1 byte. I know what removing the question mark does (it's changing the ungreedy matching to a greedy one, introducing more backtracking while avoiding lookaheads) but I can't explain why this happens. I did a benchmark but it had no impact on speed (I expected the ,+? version to be slower).
function(a){return!/^,?$|^(,,+)\1+$/.test(Array(-~a))}This will make it 54 bytes. Still longer than the 41 bytes version by p01 but I love this for how the regular expression engine is abused.
Hm, i can't see to replicate the problem. Totally works in my Opera 11.50. Still, yeah, we might save a byte there.
This actually seems to be an error in the RegExp engine of opera...
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!
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
man, this is awesome. You can omit the parenthesis inside the Array statement:
function(a){return!/^1?$|^(11+?)\1+$/.test(Array(1+a|0).join(1))};