Fun
Follow


Prime Numbers ... with a Regular Expression!

Stephen23 on 31 Oct 2024 (Edited on 2 Nov 2024 at 18:45)
Latest activity Edit by Stephen23 on 2 Nov 2024 at 18:45

I know we have all been in that all-too-common situation of needing to inefficiently identify prime numbers using only a regular expression... and now Matt Parker from Standup Maths helpfully released a YouTube video entitled "How on Earth does ^.?$|^(..+?)\1+$ produce primes?" in which he explains a simple regular expression (aka Halloween incantation) which matches composite numbers:
https://www.youtube.com/watch?v=5vbk0TwkokM
Here is my first attempt using MATLAB and Matt Parker's example values:
fnh = @(n) isempty(regexp(repelem('*',n),'^.?$|^(..+?)\1+$','emptymatch'));
fnh(13)
ans = logical
1
fnh(15)
ans = logical
0
fnh(101)
ans = logical
1
fnh(1000)
ans = logical
0
Feel free to try/modify the incantation yourself. Happy Halloween!

Tags