Menu
This line of ruby code detects prime numbers (awesome!).
("1" * n) !~ /^1?$|^(11+?)\1+$/ # where n is a positive integer
The detail is explained in this blog post http://www.noulakaz.net/weblog/2007/03/18/a-regular-expression-to-check-for-prime-numbers/
I'm curious about it's performance in the manner of BIG-O notation. Anyone help?
349
If the number is not divisible by two, the regex engine increments the divisor. (11+?) becomes 111 , and we try again. If at any point the regex matches, the number has a divisor that yields no remainder, and so the number cannot be prime.
Basically (0+1)* mathes any sequence of ones and zeroes. So, in your example (0+1)*1(0+1)* should match any sequence that has 1. It would not match 000 , but it would match 010 , 1 , 111 etc. (0+1) means 0 OR 1.
Example : The Regular expression . * will tell the computer that any character can be used any number of times. Optional character – ( ? ) This symbol tells the computer that the preceding character may. or may not be present in the string to be matched.
From empirical data it appears to be O(n2).
I ran the Ruby code on every 100th of the first 10000 primes. Here are the results:
The blue dots are the recorded times and the orange line is y = 2.9e-9 * x^2. The line fits the data perfectly, indicating that the complexity is O(n2).
This is to be expected since the regular expression checks all possible divisors to see if any of them occurs a whole number of times in the string.
191
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
