this regex identifies prime numbers (reaction)

Check out the post here: www.noulakaz.n...
To play with this regular expression yourself, try this: regex101.com/r...
My Links
shaky.sh
shaky.sh/tools
/ andrew8088

[@ccgarciab]

I think you should clarify that it works with numbers in unary. It took me until the examples to realize this, and it's the key to understand how matching is used as a stand in for division.

[@wlockuz4467]

Yeah that was a big oversight. I only realized what was going on when he go to the code.

[@scottcallaway9586]

Yeah became super obvious to me when he had four 1's on the screen and said that was "4". Should be clarified in the title otherwise it's clickbait.

[@Raiment57]

Yes! Just wasted several minutes waiting to see how on Earth this would work. Annoying.

[@Primeagen]

Ohh! You are right, group matching is doing what division would do

[@forsyth5793]

Ohhhhhhhh I wish I’d read through the comments before watching

[@megaing1322]

I think it should be mentioned that this "regex" are not actually regular expressions in that Computer Science sense: They don't define a regular language. This is because of the backreference which brings it up to a context free grammar, and then actually a repeated backreference which brings it up to a context sensitive language. Using this as an example as to why you should always be careful with your regex is slightly weird for that reason: If you are using backreferences, especially repeated backreferences, you probably shouldn't be using a regex engine for that.

[@seiryn3082]

Yeah, regex + back reference are powerful enough to solve NP-completes problems which is way more powerful than they should be

[@megaing1322]

@@seiryn3082 Really? How do those get around the polynomial space constraint? Do you have a link for that? I do believe that they cover context sensitive and even LBAs (although I am not sure about that), but isn't NP > PSPACE?

[@seiryn3082]

​@@megaing1322 You can find an article if you search for "perl regular expression NPC-3SAT"

[@antonf.9278]

​@@megaing1322NP ⊂ PSpace A simple PSpace algorithm for solving any NP problem is to do a depth first search over the possible solutions to the NP problem. The space needed will only ever be polynomial as the solution will only be polynomial and the only other state needed is the current depth.

[@mad_vegan]

I didn't know any of that. Do you recommend any video or article explaining the different types of "languages" you're talking about? And why should we avoid using regex for that kind of stuff?

[@szhzs6121]

this is a great example of a problem which you should NOT solve using regular expressions. not incidentally, that's true for 99% of problems out there.

[@SlimThrull]

"If you have a problem and you used regex to solve it, you now have two problems."

[@rudyNok]

@@SlimThrull * now

[@rafa_br34]

Yeah I rather use something "normal" other than allocate a 4gb string to test a number like 4.294.967.295(not to mention it would still need to compute the regex)

[@Skarpo89]

Sadly

[@AScribblingTurtle]

Didn't know you could use references to capture groups with in the expression itself. 😳 Interesting to see, how it interacts with the lazy/not greedy quantifier. Thanks for sharing this. 🙏

[@blockmath_2048]

TL/DW: The regex matches a composite number of "1"s. It does this by looking for A and B, where A and B are >= 2, A*B = N, and constrains them by A being (11+?) and B being \1+

[@22dunix3]

There is also tool to visualize regex, called regexper. Visually more understandable diagrams of what is going on if youre analyzing regex and not writing it yourself

[@pwhqngl0evzeg7z37]

This is pretty sick, and surprisingly intuitive. I didn't know about the +? quantifier, but after that it all made sense.

[@davidh.4944]

Support for it depends on the flavor of regex you are using, but most of the more advanced variations have some form of non-greedy syntax.

[@isomeme]

I wish more people knew about the non-greedy quantifier. It makes some kinds of matches much easier to implement, and many work-alike matches far more efficient.

[@xcoder1122]

Actually there are three official REGEX standards defined by POSIX which itself is a IEEE standard: BRE (Basic Regular Expressions), ERE (Extended Regular Expressions) and SRE (Simple Regular Expressions). But SRE is deprecated, so just forget that you've ever heard it. UNIX `grep` usually works with BRE, unless you call it as `grep -E`, then it works with ERE (`egrep` is a shortcut for `grep -E` BTW). Then came PERL and PERL created its own flavor or REGEX. Most REGEX features you see today that were not part of the POSIX standard are in fact PERL extensions. This includes non-greedy (aka lazy) matching for quantifiers (*, +, ?). Most implementations of other programming languages copied the PERL implementation usually with just a bit less features (they are all subsets of the PERL 5 implementation from 1994). Some added a few new features on their own (e.g. Python), which usually were later backported to PERL. All of them are backward compatible to ERE. Problem with lazy matching is that it is way harder to implement than greedy matching and also requires way more resources, that's why some implementation leave it out on purpose. Even modern `sed` does not support it. Note that POSIX only requires `sed` to support BRE and already supporting ERE (with `sed -E`) is a non-POSIX extension. `grep` on some systems does support `grep -P`, where P stands for PERL and in that mode it will actually support PERL extensions, including lazy matching.

[@pepkin88]

In this case of this regexp, the greediness of the quantifier doesn't matter for the purpose of finding a match, but matters for performance. For example, take 12 ones. On regex101 you'll see that the original version goes 11 steps to find a match. But the version with a greedy quantifier `(11+)` will find a match after 23 steps. (it also matched 6 ones in the group 1, instead of 2 ones) But in case of prime numbers, it doesn't matter, because no matter from where it starts looking, it has to go through all of the combinations. That's why the string of 11 ones will return no matches after 35 steps, regardless if we use `+` or `+?`. Also, in your JS, you could use something, I think, more suiting, instead of padStart :) "1".repeat(num)

[@NostraDavid2]

I took a minor where I learned to parse text via Haskell (learning Functional Programming along the way), and learning about context-free languages, regular languages, NFA, DFA, State Machines and how they relate to Regular Expressions really blew my mind. I can heartily recommend anyone take a related course.

[@NostraDavid2]

No videos for 6.005, but at least there's a book and website.

[@Schnolle]

After figuring out the unary representation of numbers, it is immediately obvious that: 1. This is an implementation of the Sieve of Eratosthenes 2. It can be simplified by removing the first half, as 1 is NOT a prime 3. Regular expressions rule!

[@isomeme]

You do need the first half, since the regex as a whole returns true for "not prime". Without the first half, 0 and 1 would return false, indicating that they are prime.

[@TheJamesM]

1. No, this is a purely naïve search for divisors. It first tests for 1, then very painstakingly checks whether any integer from 2 to n-1 divides cleanly into n. It essentially does so by iterative addition (by way of repeated backreference). 2. The pattern tests for divisibility, so the primes are the non-matches. Hence the need for the special case for 1. 3. Absolutely correct, though they should be wielded judiciously - certain combinations of quantifiers can require the engine to walk back and forth through the string recursively before it can definitively declare that no match is possible.

[@samtux762]

111 = 37 * 3 is not a prime. But the regex sais it is.

[@isomeme]

@@samtux762 , the strings aren't decimal numbers. It's a string of '1' characters, and what the regex determines is whether the length of that string is prime (returning false for primes, true for non-primes). The use of '1' as the repeating character was arbitrary, and I think it was a bad choice. I'd prefer something like 'x' to make it clear that the string doesn't represent a number.

[@thecakeredux]

@@samtux762 1 = 1, 11 = 2, 111 = 3, etc. This isn't a decimal representation, it's a *unary representation*

[@tom-kz9pb]

It is easy to write a logically correct script that can identify prime numbers. What is extremely difficult is to get the script to run fast enough to be useful, and/or not to blow away available memory, once that the numbers get very big.

[@catcatcatcatcatcatcatcatcatca]

This is also a good example how regular expressions can be unintuitively expensive computationally. I’m sure you could use similar iterative process but for all n-length substrings of characters just to ultimately match every possible string with only alphanumeric characters. Someone should make that an npm package.

[@TheBiggreenpig]

Yeah, and hopefully many lazy people will use it as a real prime finder.

[@akam9919]

@@TheBiggreenpig you love chaos...don't you.

[@darrennew8211]

Regular expressions aren't unintuitively expensive computationally. A regex can be, but a regex is much more complex than a regular expression. Regular expressions can be evaluated in linear time.

[@halimkbas2883]

I checked 13163, which is a prime. It exploded. Hahhaha

[@psriniv1]

I completely missed that we were talking about binary representations of digits here until over halfway through. Suddenly the whole thing makes so much more sense lol

[@ddichny]

Not binary, unary.

[@israelssantanna]

Absolutely fantastic! Please do more regex videos 😊

[@antoinecaron8915]

It reminded me of a similar conversion to roman numeral process where the input numbers were a expressed as a series of "I" and you're map/replace groups in sequence.. "IIIII" would become "V".. then "VV" would become X.. etc.

[@gameplaydosabao]

It is in fact fetching the entire string trying to find multiple of 2, then multiple of 3, and so on until it runs the entire string trying to mach 111… with exact repetition until the end. This means that the complexity of such method is exponential minus 1. In other words, is a brute force method with exponential growth. Don’t try to do it with larger numbers. 😂

[@jpleveille]

Tried with PHP and it will only detect primes below 49152 (48k); past that limit the subject is either too long or the capture loop exceeds some internal limit (it won't crash, it will just stop detecting primes)

[@StefanReich]

Damn it. I was hoping to find the biggest prime ever detected using this method

[@SlimThrull]

Out of curiosity, did it state how many steps it took for the last prime below 49152?

[@jpleveille]

​@@SlimThrull I don't know about number of steps, it should be easy to calculate. Starting with 49146 it returns an error "JIT stack limit exhausted" (PHP 8.0.29); to say the regex is inefficient is an understatement. I didn't try disabling JIT but read somewhere the JIT stack size for PCRE in PHP may vary between 32k and 192k (although PCRE lib recommends between 512k and 1M so :shrug:)

[@FrankHarwald]

Could you maybe put somewhere in the description that this one is supposed to match an unary number of "1"s & NOT decimal/binary numbers? Thanks

[@jacksims8018]

Definitely needed the explanation that this is neither base 10 nor binary, but a string of 1's n long where n is the number you're checking! Otherwise awesome video :)

[@nyxcode2818]

dont wanna be too pedantic, but these are not regular expressions. with the back-reference, the resulting grammar is context-free iirc.

[@andrew-burgess]

Woah, never heard of context-free grammars before, looked them up briefly just now and will explorer them more later. Thanks for pointing this out!

[@nyxcode2818]

@@andrew-burgess it's a cool rabbit hole, enjoy. It's the cornerstone of theoretical computer science. Formal languages are categorized in the chomsky hierachy, and "regular" languages are the most basic ones. I suspect RegEx started out as a regular language, but got progressively more powerfull with features like backtracking.

[@NostraDavid2]

​@@andrew-burgessregex part of bigger whole, like regular languages. Very cool. Fuck KZbin for removing the longer comment I wrote.

[@AlFredo-sx2yy]

​@@NostraDavid2​ Your comment must have been too offensive for youtube's liking. How dare you talk about regex in depth?

[@megaing1322]

Not context free, but context sensitive because the backreference is repeated.

[@chazits]

I solved a problem with regex , now I have two problems.

[@tensorflaw]

I look forward to seeing this incorporated into a widely used public repo on npm

[@AnthonyFammartino]

You should reupload and explain in the first minute of the video that this works in unary. It was not apparent until you mentioned that "1111" was the value "4". Either way, interesting video and find so thank you for the breakdown.

[@lainverse]

I guess it's cool you can do this with regular expressions. However, this is a perfect example of how to misuse a regular expression. Not only this is a horrendously slow and memory inefficient way to determine is number a prime. Not only this is an example of using regex for tasks they are not intended to do. But in billions range it start to fail with "RangeError: Maximum call stack size exceeded" since RegExp engine have its own limits and end up going too far with all these back-references. Furthermore, at larger numbers padStart/padEnd start to fail too and even wouldn't they fail you'll hit memory limit of your PC just a bit later down the line. > Some people, when confronted with a problem, think "I know, I'll use regular expressions." > Now they have two problems.

[@askegg]

I understood next to none of this, but feel smarter for having watched it.

[@mahadevovnl]

For those, like myself, who have no idea why any of this matters: Prime numbers are the hidden gems of computer science. Used in cryptography, they're the key to a lock only you have - think RSA encryption. Prime-based hashing also neatens data storage, minimising collisions and speeding up access. Finally, prime numbers grease the wheels of complex algorithms, making everything run that bit smoother. All in all, they're an essential cog in the code machine. Super interesting stuff. Though in my 22+ years of being a software engineer I've never directly used it, nor could I explain what a prime number is if you asked next week, this kind of information is priceless for people who are very deep into the actual science part of computers.

[@andrew-burgess]

Thanks for adding this! Totally missed explaining the what/why of prime numbers! Appreciate you sharing this for everyone else 💚

[@MortvmMM]

just wait until quantum computers become a thing and make all hashing algorithms and bitcoin obsolete

[@ccgarciab]

Prime numbers are important in mathematics because they can be though of as the atoms of the natural numbers: a unique product of primes makes up any other number. That property makes them omnipresent in math, particularly in number theory. Cryptography makes use of number theory and therefore of primes. But primes are important for more than cryptography.

[@xHomu]

Donno why KZbin recommended your video, but you're absolutely right, this is super cool!

[@Wolf-if1bt]

Maximum ingenuity for minimum efficiency

[@GameCyborgCh]

regex is black magic

[@ddichny]

Might help to clarify that this regex doesn't "identify primes" (i.e. it does not match primes), it matches strings that have a composite (non-prime) length. From that you can "identify primes" by what it *doesn't* match, sure, but it's confusing to leave the impression that it matches primes when the point is that it matches things that *aren't* prime.

[@SurenEnfiajyan]

^1{0,2}$|^(1{2,})\1+$ this will work too, but will probably be slower for larger numbers.

[@cmyk8964]

Oh, that’s clever. Sounds unperformative as hell, but that’s clever.

Cool video! Note: instead of using "".padStart(num, "1") or "".padEnd(num, "1"), you can juste use "1".repeat(num) in JavaScript.

[@orychowaw]

Indeed, a lot of problems become much simpler in unary notation. But as somebody already mentioned, it is a cumbersome notation...

[@TheSkepticSkwerl]

I guess the problem here, is performance and how much memory it uses

[@ManSubhu]

Taking a prime and seeing if it dvides into every possible lower prime starting from 2 seems a very inefficient way of finding primes, what am I missing?

[@youtubepooppismo5284]

Now match a string that is "1" repeated p times where p is a prime. Level: pumping lemma impossible

[@TheDmviper]

I think it's important to mention that regular expressions have some very specific rules that "regex" break. A regular expression always matches an entire string. A regular expression (RE) is: 1) a single character or the empty string 2) the concatenation of two REs 3) the alternation of two REs (one or the other) 4) 0 or more copies of an RE (known as kleene star) If you can't build the RE from these primitives it's not a RE but something else. The benefit is that real REs always run in O(n) time, which is why we care to make the distinction at all

[@KojiKazama]

I always thought it was pronounced reg ex. "reg" for regular. I see now it is actually quite common to say rejex.

[@darrennew8211]

Probably better to say rejex, since what a regex matches isn't regular. ;-)

[@InverseTachyonPulse]

The dark side of the Force is a path to many abilities some consider... unnatural 👀

[@anafro_ru]

Wow The question is: is regex faster than classical prime number function? Like looping thought i = 2 to i = sqrt(n) (afaik)

[@siborgium9022]

No. It uses backreferences, which are extremely slow. It can't use integers and in general efficient number representation, can't use proper math, and it uses much more memory to store the NFA itself and matches. It has to be compiled and fed a specific number representation. Looping, on the other hand, is simple and efficient, not to mention numerous algorithmic optimizations to the process.

[@anafro_ru]

@@siborgium9022 thank you so much for this descriptive explanation! I really appreciate it ☺

[@andrew-burgess]

For sure. For me, this is mainly about learning a creative way to combine a lazy quantified and a back reference. Definitely not discovering new primes with this 😂

[@anafro_ru]

@@andrew-burgess haha, I would benchmark this just for fun 🤣

[@wadecodez]

Yes and no. This is like asking if a function is faster than a lambda. Regex is like shorthand for programming. You can easily write sluggish regular expressions just like you can easily write sluggish loops. It all comes down to your understanding of time complexity.

[@henrym5034]

The site is now under maintenance. Look what have you all done.

[@SlimThrull]

Clever for sure. But the amount of processing power needed to figure out large numbers is absurdly high.

[@mepipe7705]

i feel clickbaited, because the regex does not identify prime numbers in general but only a prime count of digits...

[@Jkauppa]

easily amused

[@IantoCannon]

I tried this as a search in vim and I got "E65: Illegal back reference". Is this only in perl? What type of value does it return?

[@Escviitash]

The title of this video sound to me like you can enter a number, e.g 252, to see if it is prime. According to the explanation there will be no match if the entered number is prime. 252 will also create no match which by the same logic should therefore be prime. In fact any number that are not a composite number of 1 will be prime by that logic. A little challenge. Determine whether the number 1000000007 is prime using only this function. It will only require a string of 1s that are 240 times longer than the total number of letter in the combined works of Shakespeare

[@Yotanido]

This is pretty awesome. I have to say, though, this is stretching the definition of "regex". If you use back references, it's not exactly regular, is it.

[@darrennew8211]

Apparently, the convention now is to call it a "regex" if it's not regular, and a "RE" or "regular expression" if it is.

[@MadsterV]

I wonder about the performance of this....

[@wChris_]

This Unfortunately only works for unary numbers and it in fact does not match primes, but rather composite numbers. But to top it all of its not even regular! (this is because of the back reference!)

[@erikkonstas]

Not all regexes define regular languages, even though the same term is used...

[@lucass8119]

@@erikkonstas A regular expression SHOULD recognize only a regular language, in the strict sense. But, as usual, library implementations have nice to have features. Which... makes them not really regular expressions. But it doesn't matter, because they're more powerful and everyone likes it.

[@agamkohli3888]

This is not a regular expression since you use the backslash

[@s1l3nttt]

Thank God chatgpt abstracts all this away

[@CarrotCakeMake]

As others have said, not a regular expression. Just a pattern.

[@ajinrenfire]

hey 👋, what is the font used for commenting the code?

[@420theriddler]

The worst way to check for prime number.

[@simonwillover4175]

/^(11+)(11+)+$/ is simpler, but a litttle bit slower due to the greediness.

[@andriib9390]

This is cool, but the title is trying to make it sound cooler. It is VERY important that it is unary. I think a lot of people with math background would have come up with this solution easily if the qestion itself would be more accurate. This should be stated either in title or before explaining a solution, as a hint for example: "use unary"

[@andriib9390]

It can even be called "prime test using regexp" instead of "regexp that identifies prime number", that would be more accurate. When word number is used in the context of regexp it is almost always perceived as something like \d+ (decimal integer), and in this case this regexp does not identify such numbers

[@davidellsworth4203]

My mind was blown too, when I found out about this in 2014. I was so fascinated that I went on to extend it to many more number sets and functions, most of which I posted on code golf StackExchange as username Deadcode. If you Google "Match correct statements of multiplication" (with quotes) it'll bring up a summary. I've also recently written a .NET regex that matches prime numbers in decimal instead of unary.

[@gliaMe]

Is it rejex or regex? It's like jif vs. gif to me.

[@davidissel7980]

Not a very useful regular expression. It quickly becomes too expensive (memory wise). You're using 1 to represent 1, 11 to represent 2, 111 to represent 3, 1111 to represent 4, etc. You'll run out of memory long before you are able to test any interesting numbers for primeness.

[@nukularius]

Strictly speaking this is not a regular expression since regular expressions can be checked by finite automata and allow no back references. Perl (and most programming languages) just name this wrongly.

[@jammin023]

"identifies prime numbers" suggests that it's a good way of *finding* them. It's not. This regex *tests whether or not a given number n is prime* (after that number has been expressed as a string of n 1s) - and does so in just about the least efficient way possible. After making sure it's not 0 or 1, it literally just brute-force tests whether n is a multiple of 2, then 3, then 4, and so on all the way upto n (or maybe half-n depending on whether the regex engine is smart enough to stop backtracking at that point). Any sensible prime-testing algorithm, if it's already found that n is not a multiple of x, would not bother checking if it's a multiple of a multiple of x. e.g. if the candidate number is not a multiple of 2, it won't be a multiple of any other even number either so you can skip them all, but this algorithm is too dumb to do that. It's an interesting case study of what can be done in regex, but please don't actually use it for real...

[@gFamWeb]

I prefer regexr over regex 101, but both look cool!

[@cvoges12]

Um, no, this is not true. This fails to recognize many prime numbers and falsely assumes many non-prime numbers are prime. You go on preaching unit tests but you didn't even unit test the regex enough to know it didn't work. Also, it is pronounced "reg ex" not "reJ ex" as it is derived from "REGular EXpression". And you failed to also mention that these aren't regular expressions but an extended regular expression. Capturing and such are not a part of regular expressions.

[@olivier2553]

I like using The Regex Coach that need no connection to work. It's a windows utility but works fine in wine.

[@felipedidio4698]

Man, this really feels like not a regular language.

[@charonme]

you are right en.wikipedia.org/wiki/Regular_expression#Patterns_for_non-regular_languages

[@TheGreatAtario]

Rejex?

[@joshuagillis7513]

This entire video is misleading. What he proves is that this regex identifies numbers that are NOT prime. There is nothing here that proves that a number that doesn't match this regex IS prime. All numbers matching it are by definition multiples of 2, but not all non multiples of 2 are prime.

[@jeffvenancius]

Really cool, but I'm imagining it doesn't scale really well with big numbers?

[@jeffvenancius]

Oh.... But if you need to convert in unary you could also do the conversion from binary(?) With some tweaks, of course

[@9799ms]

nice vid but pls make it in dark mode.. My eyes are hurting

[@Serhii_Volchetskyi]

Looks like it’s using regex as virtual machine. Nice! But it’s searching from 0 to n, which is less effective then searching from 0 to sqrt n. Nice try, though!

[@WinterHoax]

If i do like a 100 digit number will say whether it is prime in like no time like less than 1 ms?

[@daliasprints9798]

A non-regular expression.. 🤔🙃

[@michaelbauers8800]

head...hurts, lol. But very cool

[@tinyBigGAMES]

NICE!

[@The1RandomFool]

It's interesting, but man is it horribly inefficient and impractical for speed and memory usage. I tested it in Python against Sympy's isprime function. I also tried Rust, but \1 is not supported in Rust's regular expression.

[@bertilow]

Not supported?? So Rust is not a usable language then. I'm shocked.

[@saxtant]

Great, I think we have the first quantum mechanical safe primality test, there goes everyone's private keys!

[@ChrisBigBad]

FM Fucking Magic TM!

[@nigelhewitt]

Wonderful... ...but boy is it slow.

[@davestorm6718]

Using this to test for primes is really the worst way to do it. Similarly, using recursion for finding Fibonacci numbers is the worst way (I got a coding answer "wrong" on a job interview by using a Fibonacci equation with the golden ratio, even though it was much faster and could handle nth numbers higher w/o loading down the CPU. Needless to say, my cleverness was discounted by the idiot interviewer who couldn't wrap her head around any other solution besides recursion.

[@kennethbeal]

Thank you!

[@joshuagillis7513]

Im giving this video a thumbs down for mathematical dishonesty. This regex doesn't identify primes as the title would lead you to believe. It just tells you what isn't a prime

[@chennebicken372]

I think, it should be forbidden to use Regular Expressions that don't describe Regular Languages... Every Regular Language has a DFA, that accepts every word in it and rejects everything else. Sorry to say, but there is no Derterministic Finite Automaton wht can determine if a number is composite. That's why I don't like this extension of Regular Expression. They aren't regular.

[@mycroftholmesiv]

Most languages use CFG(Context Free Grammers) rather than DFAs/NFAs, which allow them to solve/recognize patterns larger than DFA/NFAs. Pure math CFGs can recognize a to the N b to the N patterns, where N is a number. DFAs and NFAs can't be designed to solve that (it would require infinite space to solve, and DFAs and NFAs are, by definition, limited to a finite space).

[@Enkrod]

Understanding of the video is impossible until the realization of unary notation. Things like that need to be explained earlier, or the video is just clickbait, no matter how cool this is. Blocking your channel.

[@MMarcuzzo]

Wow.

[@saumyacow4435]

Two takeaways here: 1. Regular expressions are way cool 2. Never, ever use regular expressions, especially when you care about unexpected behaviour, bugs and typos. Never.

[@GustvandeWal]

Point 2 is just stupid. I use them every single day and would be screwed without them.

[@saumyacow4435]

@@GustvandeWal We salute your bravery :)

[@yaroslavpanych2067]

I'm definitely not dumb. How exactly it will check if number 123412321 is prime? It will fucking not! So again, wtf with the title?

[@aurynaichi7030]

Lost me at 1.

[@soanvig]

Clickbait...

[@deatho0ne587]

Is it cool that you can use regex, 100% Should this replace any of the other Prime methods, Not at all. Regex are generally slower than doing it a slightly different way.

[@yasscat5484]

clickbait

[@JamesSmith-ix5jd]

What implementation of regex is it? That's what I don't like about regex, too much incompatibe crap, I don't like python for the same reason, and javascript, and gnu, and shells and many other things, lots of crap, the whole cs is science of crapware

[@andrew-burgess]

That escalated quickly.

[@FunctionGermany]

woa

[@GoldenLion5648]

Regex101 is great, though if you prefer learning through games, another cool way to get familiar with regular expression is the game Regex Adventure ;-) (shameless plug)

[@geert5811]

You have a problem? Use a regular expression, now you have two! g.

[@markzuckerbread1865]

Sieve of Eratosthenes? Trial division? Just use Regex bro 🗿

[@GuruEvi]

This seems to me to be the sieve of erastothenes method (mark every multiple of 2 and subsequent matches of the regexp as not prime until n), just using RegExp as the language (which is in itself as a language Turing complete)

[@markzuckerbread1865]

@@GuruEvi interesting, because honestly I didn't understand how it worked :))

[@TerrexoDesign]

@@GuruEvi this is actually just dividing by all numbers...

[@ccgarciab]

@@GuruEvi standard regex is not Turing complete. Do they reach completeness with Pearl extensions and so on? Sounds implausible to me Also, the algorithm used in the video is just trial division.

[@ilangated]

@@GuruEvi regex aint turing complete

[@henrycgs]

Having once proven mathematically for a computer theory assignment that it was literally impossible for regular expressions to find prime numbers, this immediately caught my eye. Luckily, it doesnt break maths: this has much more memory of the string than a formal regex should have, as it remembers the number of ones in the first match.

[@marv4054]

can you share a link of that proof? seems like an interesting read

[@IStMl]

@@marv4054 you prove the language of prime numbers is not regular

[@ApplepieFTW]

I don't exactly know how this would have much more memory of the string than a formal regex (what is a "formal" regex) should have

[@СергейМакеев-ж2н]

I think this is at least a context-sensitive grammar, if not worse than that. I mean, the operation "repeat the previously captured string" is literally *sensitive* to the *context.* But maybe it doesn't even fit the CSG class.

[@henrycgs]

@@marv4054 I don't have one right now, but it's not too difficult. First, you need to understand what a regular language is. A "language" is any set of strings. A "regular language" is a language in which all of its strings can be "generated/recognized" by simple state machines. (omitting a lot of things for simplicity) Formal regular expressions are a way to describe those languages/state machines. What we commonly refer to as "regex" is a specific syntax/implementation based on the theoretical background of these formal expressions. One can, after some thought, prove a few things about regular languages. One of them is that if you have an infinite language (one with infinitely many unique strings), there must be a point at which they're all just repeating one identical middle bit forever. In other words, they can't get more complicated than a starting bit, some repetition, and an ending bit. More importantly, for any number after some point, there exists a string in this language with this middle bit repeated this number of times. Well, think of the language of the prime numbers. It could be {"2","3","5"...} or {"11","111","11111"...}, it doesn't matter how you represent it. It would be very convenient if there was a point after which every single prime number was just an identical beginning, end, and a repeating middle bit, right? Imagine how easy it would be to generate prime numbers! just add another repetition and you got the next. Sadly, it's very obvious that this isn't the case, and there are many ways to prove this. Therefore, it's impossible for a regular expression to identify prime numbers, because that would mean that the language of prime numbers is regular, and that would mean that the primes follow a very obviously wrong dumb pattern. Does the regex in this video show that I'm wrong? No, it just shows that regexes aren't REALLY regular.

[@aelolul]

I am reminded by the book _Gödel, Escher, Bach_ which uses a technique similar to this to discuss the nature of mathematical proofs using nothing but typographic symbol manipulation. If you haven't heard of it, I highly recommend the book.

[@Slgjgnz]

That was the first book that kinda broke my mind in an interesting way. I need to find it again.

[@fllthdcrb]

@@Slgjgnz If it helps, the full title is _Gödel, Escher, Bach: An Eternal Golden Braid,_ and the author is Douglas Hofstadter.

[@reginaldfrank656]

Bro the pipe is not a Boolean or, it's a set union. Each regular expiration defines a language which is a set of strings. The pipe combines two separate expressions into one whose language is the union of the two expressions.

[@MultiUltimater]

For those of you still wondering how this works, the regex expects a unary representation of a positive integer. The real magic is \1+ which matches the first group again one or more times which emulates trying to count by 2's, then by 3's, etc. For example 9 is not prime since it is divisible by 3. And the regex would return true indicating it's not prime. Why? When the regex gets up to counting by 3's, and group 1 would look like this: (111), the \1+ would match group 1 an additional one or more times. When the \1+ is repeated twice, we have the whole expansion (111)111111 and thus the regex returns a match, indicating 9 is not prime. In practicality, you wouldn't use a regex for this as it's very expensive and would hit a memory limit much sooner than a non-regex approach. Similar logic could be implemented in JavaScript like so which doesn't rely on a regex: function isPrime(n) { if(n < 2 || Math.floor(n) !== n) { return false; } for(let i = 2; i < n; i++) { if(n % i === 0) { return false; } } return true; }