8 ms·
A regular expression to check for prime numbers (2007)
- ufo 3y agoWhy does it have /^1?$/ ? Wouldn't that accept 0 and 1 as primes?
- wongarsu 3y agoThe regular expression matches all non-primes (in base 1 encoding). 0 and 1 are not prime, so it matches them.
- rperce 3y agoI 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) I agree that the article formatting is a bit misleading.
- vignesh_warar 3y agoInteresting! If anyone is seeking a math formula for primes, here is one: https://en.wikipedia.org/wiki/Formula_for_primes 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 https://www.youtube.com/watch?v=j5s0h42GfvM
- albert_e 3y agoThanks for sharing the video was very interesting
- venusenvy47 3y agoThat's cool. I had no idea there was a symbol for the floor function.
- shric 3y ago(2007) Previous discussions (with >25 comments): 2015: https://news.ycombinator.com/item?id=9039537 https://news.ycombinator.com/item?id=9039537 (67 comments) 2022: https://news.ycombinator.com/item?id=30564287 https://news.ycombinator.com/item?id=30564287 (121 comments)
- dang 3y agoThanks! Macroexpanded: A regular expression to check for prime numbers (2007) - https://news.ycombinator.com/item?id=30564287 https://news.ycombinator.com/item?id=30564287 - March 2022 (121 comments) A regular expression to check for prime numbers - https://news.ycombinator.com/item?id=9039537 https://news.ycombinator.com/item?id=9039537 - Feb 2015 (67 comments) A regular expression to check for prime numbers - https://news.ycombinator.com/item?id=1486158 https://news.ycombinator.com/item?id=1486158 - July 2010 (13 comments) Regex to check for prime numbers - https://news.ycombinator.com/item?id=707236 https://news.ycombinator.com/item?id=707236 - July 2009 (9 comments) A regular expression to check for prime numbers - https://news.ycombinator.com/item?id=58780 https://news.ycombinator.com/item?id=58780 - Sept 2007 (8 comments)
- tylerhou 3y agoTechnically 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.
- CoastalCoder 3y agoAgreed. 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.
- wongarsu 3y agoWhen programmers say regular expression they usually mean Perl Compatible Regular Expressions (PCRE). Or I guess PCRE-compatible expressions, since there are other implementations of the same syntax out there. If you go back far enough in time they were once regular expressions in the computer science sense, but then features got added, and now they are incredibly powerful but can take basically infinite memory and time. https://en.wikipedia.org/wiki/Perl_Compatible_Regular_Expressions https://en.wikipedia.org/wiki/Perl_Compatible_Regular_Expres...
- disconcision 3y agofunnily enough the original POSIX regular expressions (BRE) were strictly less powerful than regular expressions (CS sense), lacking a general alternation operator (though one was provided in ERE)
- chrismorgan 3y agoAlthough general PCRE syntax has clearly won, that’s distinct from the infinite-memory-and-time matter. Engines that don’t use backtracking and can search in linear time (O(regex-size × search-text-size)) have been making a serious comeback in recent years, at only the cost of not supporting lookaround assertions or backreferences. For example, the re2 library, or Rust’s regex crate, both of which are very popular.
- lovegrenoble 3y ago[flagged]
- pkoird 3y agoClever! 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.
- shagie 3y agoCorrect. The \1 holds some external state... but this can be overcome with a different architecture. If you want to start down that rabbit hole. Extending finite automata to efficiently match Perl-compatible regular expressions https://www.researchgate.net/publication/221325349_Extending_finite_automata_to_efficiently_match_Perl-compatible_regular_expressions https://www.researchgate.net/publication/221325349_Extending... > Regular expression matching is a crucial task in several networking applications. Current implementations are based on one of two types of finite state machines. Non-deterministic finite automata (NFAs) have minimal storage demand but have high memory bandwidth requirements. Deterministic finite automata (DFAs) exhibit low and deterministic memory bandwidth requirements at the cost of increased memory space. It has already been shown how the presence of wildcards and repetitions of large character classes can render DFAs and NFAs impractical. Additionally, recent security-oriented rule-sets include patterns with advanced features, namely back-references, which add to the expressive power of traditional regular expressions and cannot therefore be supported through classical finite automata. > In this work, we propose and evaluate an extended finite automaton designed to address these shortcomings. First, the automaton provides an alternative approach to handle character repetitions that limits memory space and bandwidth requirements. Second, it supports back-references without the need for back-tracking in the input string. In our discussion of this proposal, we address practical implementation issues and evaluate the automaton on real-world rule-sets. To our knowledge, this is the first high-speed automaton that can accommodate all the Perl-compatible regular expressions present in the Snort network intrusion and detection system. ---- The awkward part is that a PCRE is demonstrably more powerful than a regular language, but not as powerful as a CFG (you can write CFGs that can't be matched by a PCRE - ([{}]) matching, a^nb^n and so on). So the question that gets interesting is "can every PCRE be matched by a CFG?" Is it a fork? or is it a non-integer language? https://en.wikipedia.org/wiki/Chomsky_hierarchy https://en.wikipedia.org/wiki/Chomsky_hierarchy > Note that the set of grammars corresponding to recursive languages is not a member of this hierarchy; these would be properly between Type-0 and Type-1. So there's a language between the Turing machine and the linear bounded Turing machine that matches a context sensitive language. Is the PCRE something between Type-2 and Type-3? or is it a Type-3+I? https://en.wikipedia.org/wiki/Formal_grammar#Other_forms_of_generative_grammars https://en.wikipedia.org/wiki/Formal_grammar#Other_forms_of_... > Many extensions and variations on Chomsky's original hierarchy of formal grammars have been developed, both by linguists and by computer scientists, usually either in order to increase their expressive power or in order to make them easier to analyze or parse. ...
- bighoki2885000 3y ago[dead]
- deleted 3y ago[deleted]
- aenis 3y agoIn case anyone is wondering, gpt4 provides the same solution. It takes some prodding though, and you get treated with a lecture of how inefficient it is before it provides the solution. "Apologies for any confusion before, and I understand the nature of your request now. It's a fun challenge to think about! While it's not practically useful or efficient, and it is actually quite limited, a creative theoretical solution exists that involves regular expressions. This specific solution only works for very small numbers due to the inherent limitations of regex. It's based on the principle that a number is prime if it cannot be expressed as a product of two smaller natural numbers. We represent the number as a repeated string of 1s, then check for repeating sub-patterns. For instance, this Perl regex checks if a number, represented as unary (a string of 1s), is prime: perl Copy code /^1?$|^(11+?)\1+$/ In this regex: ^1?$ checks for the case where you have zero or one '1', which represent the numbers 0 and 1, neither of which are prime. ^(11+?)\1+$ attempts to match the input with a repeating group of '1's. If a match is found, the number is not prime, because a repeating subgroup of '1's represents a divisor. This pattern should be used in a negative sense: if a string of 1s (representing your number in unary form) matches this pattern, it's not prime. If it doesn't match, then it is prime. Again, this is quite impractical for real use cases as the unary representation is extremely inefficient, and the computation grows quickly with larger numbers, but it's a neat way of showing how flexible and powerful regular expressions can be."
- neilk 3y agoThe original exegesis, which prompted this blog post, was by me. I am currently transitioning to a different blog engine, so the page is offline right now, but it's still available here https://web.archive.org/web/20220513113609/neilk.net/blog/2000/06/01/abigails-regex-to-test-for-prime-numbers/ https://web.archive.org/web/20220513113609/neilk.net/blog/20...
- krupan 3y agoMuch better explanation, thank you
- raldi 3y agoA better title would be “A regex to check if a string contains a prime number of characters”
- remram 3y agoI think it checks the opposite, it matches if it's not prime.
- hoytech 3y agoYou can also factor integers with Regexp::Exhaustive: https://metacpan.org/pod/Regexp::Exhaustive#Finding-all-divisors https://metacpan.org/pod/Regexp::Exhaustive#Finding-all-divi... And if you're in Toronto in 3 weeks time, come see Abigail (the original inventor of the prime number regexp) solve the N-Queens problem with regexp: https://tprc2023.sched.com/event/1LhoB/the-n-queens-problem-by-regexp https://tprc2023.sched.com/event/1LhoB/the-n-queens-problem-...
- jimhefferon 3y agoThank you for crediting Abigail.
- stevage 3y agoTook me a while to realise that it is not actually validating whether a given number is a prime number or not. It is validating whether a string of consecutive 1's has a prime length. In other words, it can't tell whether "3" is prime, unless you express it as "111". Much less exciting.
- stefncb 3y agoThink about it a different way: the regex thing can only deal with unary numbers, like your computer can only deal with binary. It's really no different. I'm not sure if you can write a decimal-to-unary converter in regex but I reckon it's possible. At least using the non-regular regex like the original prime program did.
- tiborsaas 3y agoSorry, but how is this different than pointing to three apples and explaining someone that this is what three is? Would you say it's not three because they are apples? I think it does not really matter how you represent the number. After all, all you see on your screen is "fake" it's just binary under the hood.
- comonoid 3y agoYou can certainly do calculations with apples, but doing RSA encryption with them is just impractical.
- IshKebab 3y agoIt's less interesting because decoding decimal numbers with regex is a much more impressive feat.
- cubefox 3y agoThe problem with the unary numeral system is that numerals grow linearly with value, while for binary (ternary etc) they only grow logarithmically. So they need much less space and can be much faster read and written. An algorithm with relies on unary numerals probably has worse computational complexity than one that uses binary or higher.
- sytelus 3y agoStunning: https://chat.openai.com/share/367fd09d-79cb-4683-a179-e253a8b468f3 https://chat.openai.com/share/367fd09d-79cb-4683-a179-e253a8...
- medv 3y ago> To know this, the function first generates “1111111” Not that interesting.
- underdeserver 3y agoPeople are commented "It's not a breakthrough! It's not CS-y _regular_ expressions!" I suggest relaxing, everyone. It's a fun story, not a groundbreaking discovery.
- hospitalJail 3y agobtw I found it strange that Excel has no built in way to do Re... That is a pain.
- dmd 3y agoAlso fun, if not anywhere as clever: perl -le '$_=1;print&&s/((\d)\2*)/length($1).$2/ge while length()<64'