A regular expression to check for prime numbers (2007)
1–10 of 102 posts
Re: A regular expression to check for prime numbers (2007)
#2Why does it have /^1?$/ ? Wouldn't that accept 0 and 1 as primes?
Re: A regular expression to check for prime numbers (2007)
#3Why does it have /^1?$/ ? Wouldn't that accept 0 and 1 as primes?
The regular expression matches all non-primes (in base 1 encoding). 0 and 1 are not prime, so it matches them.
Re: A regular expression to check for prime numbers (2007)
#4Interesting!
If anyone is seeking a math formula for primes, here is one: https://en.wikipedia.org/wiki/Formula_for_primes
There is also a good YouTube video that explains this: https://www.youtube.com/watch?v=j5s0h42GfvM
Re: A regular expression to check for prime numbers (2007)
#5Why does it have /^1?$/ ? Wouldn't that accept 0 and 1 as primes?
I encourage you to re-read the article: you check that the number does not match the regex:
> Is 7 prime?
>
> To know this, the function first generates “1111111” (from “1” \* 7) and tries to
> see if that string does not match /^1?$|^(11+?)\1+$/. If there is no match, then
> the number is prime.
>
> Notice that the regular expression has two parts (separated with the vertical bar |).
>
> The first part is /^1?$/ is trivial and matches with beginning of line (^), an
> optional 1 (1?) and end of line ($) which implies that it matches either the
> empty string or “1”. This simply indicates that calling that function with n==0
> or n==1 will correctly return false (as the “1” \* n will match with the first
> part of the regular expression)
Re: A regular expression to check for prime numbers (2007)
#6(2007)
Previous discussions (with >25 comments):
2015: https://news.ycombinator.com/item?id=9039537 (67 comments)
2022: https://news.ycombinator.com/item?id=30564287 (121 comments)
Re: A regular expression to check for prime numbers (2007)
#7Technically not a regular expression, as (intuitively) the backreference has to “count” the number of 1’s that were matched. Regular expressions are equivalent to finite state machines, which cannot count arbitrarily high (any state machine that can count arbitrarily high needs an infinite number of states, since there are infinite natural numbers).
The 2022 discussion has a more formal proof using the pumping lemma.
Re: A regular expression to check for prime numbers (2007)
#8[flagged]
Re: A regular expression to check for prime numbers (2007)
#9Clever! I'm kinda being pedantic but I guess using \1 makes it a non-regular expression? I'm not even sure if it's CFG anymore.
Re: A regular expression to check for prime numbers (2007)
#10Technically not a regular expression, as (intuitively) the backreference has to “count” the number of 1’s that were matched. Regular expressions are equivalent to finite state machines, which cannot count arbitrarily high (any state machine that can count arbitrarily high needs an infinite number of states, since there are infinite natural numbers). The 2022 discussion has a more formal proof using the pumping lemma.
Agreed. I read the post because the result was so shocking.
TIL that the computer-sciencey definition of RE isn't the only one in use.