Performing a Miller-Rabin primality test or filling a Sieve of Eratosthenes will almost always be the way to go. However, this line of code seems like magic and that's kind of impressive.
Regular Expression That Checks If A Number Is Prime
91–100 of 117 posts
Re: Regular Expression That Checks If A Number Is Prime
#92how many problems do we have now?
Approximately n / ln n according to https://en.wikipedia.org/wiki/Prime-counting_function
Re: Regular Expression That Checks If A Number Is Prime
#93Why does the example given by the author with L=15 state that the regex matches once it reaches 5, instead of 3? > So first, we’ll be testing the divisibility by 2, then by 3, then by 4 and then by 5, after which we would have a match.
It tests from the highest number first I believe. >> As a heads-up, I just want to say that I’m lying a little in the explanation in the paragraph about the ^(..+?)\1+$ regex. The lie has to do with the order in which the regex engine checks for multiples, it actually starts with the highest number and goes to the lowest, and not how I explain it here. But feel free to ignore that distinction here, since the regular…
Right, that makes sense. But in the explanation they go from 2, to 3 to 4 to 5, following along with the lie, yet picking the real solution. It's a bit confusing.
Re: Regular Expression That Checks If A Number Is Prime
#94Earlier quoted context omitted.
What do you mean by "non trivial base?"
Oh, just as opposed to unary. Writing numbers in the ordinary way in any ordinary base, which is to say, bases greater than 1; base 2, base 3, base ten, whatever.
It's worth pointing out that we are talking about representing numbers in unary, though. Or even more directly, plain ol' string length since the RE under discussion doesn't even care what symbols you are using, so "11111" = "abcde" under this RE.
Re: Regular Expression That Checks If A Number Is Prime
#95Earlier quoted context omitted.
Oh, that was probably it. That would be true if we were talking about FIFO queues :)
I'm another one who thinks the letter "in front" is the one that comes first. May I ask how you were thinking about the "front" and "back" of text?
Well, we read from left to right, naturally that is the order of the letters, so the one on the right is "in front" of the left one.
Re: Regular Expression That Checks If A Number Is Prime
#96This regexp is totally brilliant. It solves this problem in an unexpected way, because you think numbers, but the solution thinks strings. Not only that, the paradox, or its beauty, is that it goes to the root of the number abstraction: counting sticks.
I explored this technique some years later to solve a bunch of other problems, coprimality, prime factorization, Euler's phi, continued fractions, etc. (see https://github.com/fxn/math-with-regexps/blob/master/one-lin...).
Re: Regular Expression That Checks If A Number Is Prime
#97Earlier quoted context omitted.
I'm another one who thinks the letter "in front" is the one that comes first. May I ask how you were thinking about the "front" and "back" of text?
Well, we read from left to right, naturally that is the order of the letters, so the one on the right is "in front" of the left one.
>Well, we read from left to right, naturally that is the order of the letters
So that means "W", "e", "l", and "l" are in positions 1, 2, 3, and 4 respectively? The "W" comes first?
Isn't the first position always in front of the second by definition?
Re: Regular Expression That Checks If A Number Is Prime
#98how does it fare on time complexity compared to normal tests like say AKS?
It's very clever, but obnoxiously slow. It's useful for code golf and as a pretty impressive party trick. But like your banker will not be impressed with your college funding plan of pulling a quarter out of his ear, this is not going to make it in any real use.
Imagine naive absolute-beginner-programmer trial division. This is worse. Now add the overhead of counting via regex backtracking and integer comparison via matching strings. A fair number of regex engines will also start using enormous amounts of memory.
AKS is of theoretical interest, but not really a "normal test." It's very slow in practice, being beat by even decent trial division for 64-bit inputs (it's eventually faster, as expected, but it takes a while). But it is quickly faster than this exponential-time method. The regex is in another universe of time taken when compared to the methods typically used for general form inputs (e.g. pretests + Miller-Rabin or BPSW, with APR-CL or ECPP for proofs).
As others have noted, "has been popularized by Perl" is because it was created by Abigail, who is a well-known Perl programmer (though almost certainly a polyglot). It's also been brought up many times, though it's a nice new blog article. I hope the OP found something better when "researching the most efficient way to check if a number is prime." In general the answer is a hybrid of methods depending on the input size, form, input expectation, and language. The optimal method for a 16-bit input is different than for a 30k-digit input, for example.
Re: Regular Expression That Checks If A Number Is Prime
#99Earlier quoted context omitted.
I'm another one who thinks the letter "in front" is the one that comes first. May I ask how you were thinking about the "front" and "back" of text?
Well, we read from left to right, naturally that is the order of the letters, so the one on the right is "in front" of the left one.
[deleted]
Re: Regular Expression That Checks If A Number Is Prime
#100> How would we go about that? Well, all we have to do is add ? in front of the +. This will lead us to the regex. I was very confused until I realized the author's definition of 'in front' wasn't the same as mine...
What do you mean? Could you please clarify that? What did your understand by "in front"?
So your definition of "in front" is synonymous with "after" or "behind"?