Primality Test Using Regex

[davidktw]

https://www.noulakaz.net/2007/03/18/a-regular-expression-to-check-for-prime-numbers/

print "$ARGV[0] is ", (1x$ARGV[0]) =~ /^1?$|^(11+?)\1+$/ ? "not " : "", "a prime number\n";

 

[davidktw]

The person whom comes up with this regex for primality test demonstrated ingenuity.
It basically performed a search for NxM where N>1 and M>1.

For those whom may find this regex daunting. Basically
(11+?) is looking for N where N > 1 since there must be at least 2 '1's for this regex to match.
(11+?)\1+ is basically looking for MxN since \1 is a back reference to the matched (11+?) result. it has to be NNNNNN..... for M times and M Is also at least 2 times.

With the backtracking behaviour of regex, the regex engine will attempt to match exhaustively for any possible NNNNNNNN....N <--- total M times. N can be any number of "1s" but there must always be >=2 sets of N(1s).

That is why 9 -> NNN -> 3N x 3M, while 8 -> NNNN -> 2N x 4M. While 8 can be expressed as 4x2, but in the case of this regex, it will not match since it is non-greedy for (11+?).

On the other hand, if you use this slightly changed regex, which I have verified to be working too /^1?$|^(11+)\1+$/, it will match 4Nx2M for 8, 5N*2M for 10.

 

[peterchan75]

For large number, this regex will encounter recursion limit of 32k.
The following code is still good.

    $divisors = 0;
    $number = 1000033;
    for (my $j = 1; $j <= $number; $j++) {
        if (($number % $j) == 0) {
            $divisors++;
        }
    }
   
    if ($divisors == 2) {
        print "$number is a primer number\n";
    } else {
        print "$number is not a primer number\n";
    }

 

[davidktw]

For large number, this regex will encounter recursion limit of 32k.
The following code is still good.

    $divisors = 0;
    $number = 1000033;
    for (my $j = 1; $j <= $number; $j++) {
        if (($number % $j) == 0) {
            $divisors++;
        }
    }
   
    if ($divisors == 2) {
        print "$number is a primer number\n";
    } else {
        print "$number is not a primer number\n";
    }

I think you are missing the point. There is nothing efficient about the regex technique for this purpose. I wouldn’t even use it for any practical purpose, not to mention hitting the recursion limit. It is just to demonstrate the modelling of a problem into different form and solving the same problem in techniques meant for the alternate form. There are much more efficient primality test techniques already found today.

 

[peterchan75]

I think you are missing the point. There is nothing efficient about the regex technique for this purpose. I wouldn’t even use it for any practical purpose, not to mention hitting the recursion limit. It is just to demonstrate the modelling of a problem into different form and solving the same problem in techniques meant for the alternate form. There are much more efficient primality test techniques already found today.

Other then regex fanciness, it has little practical value.
By adding this line within the loop, it's even faster.

if ($divisors > 2) {last;}

 

[davidktw]

Other then regex fanciness, it has little practical value.
By adding this line within the loop, it's even faster.

if ($divisors > 2) {last;}

Not fast enough. There are already probabilistic primality tests out there to quickly rule out composite numbers before you spend time to engage in ascertaining the number is prime or not.

There is a specific reason for me sharing this technique. it is the demonstration of how one can model a problem into different mode. This is the practical part of thinking out of the box, it has nothing to do with efficiency.

Like I have said, you are missing the point when you discuss about limits and efficiency.

 

[peterchan75]

Not fast enough. There are already probabilistic primality tests out there to quickly rule out composite numbers before you spend time to engage in ascertaining the number is prime or not.

There is a specific reason for me sharing this technique. it is the demonstration of how one can model a problem into different mode. This is the practical part of thinking out of the box, it has nothing to do with efficiency.

Like I have said, you are missing the point when you discuss about limits and efficiency.

I was sharing in another forum about an algorithm do the job without restricting to a single task. But the forum admin said, single task approach is simple and neat. I suppose there is similarity here.

 

[davidktw]

I was sharing in another forum about an algorithm do the job without restricting to a single task. But the forum admin said, single task approach is simple and neat. I suppose there is similarity here.

Nope, no similarities here. The intention of this demonstration is on the mind to think out of the box, to get out of the local maximal first. Without taking this step, you wouldn’t be able to find a better technique even if it exists because it takes an adventurous mind to find something outside its comfort zone.

Again I stress, it is not about efficiency that I am sharing right from the first post. I have already mentioned about the practicality of the technique when I reply you earlier.

When you need to search for something exhaustively, it is hardly efficient. That is what this regex does, but this technique requires a remodeling of the same problem into a different space. That is why I think this solution is interesting, not because it is practical or fast.

In any case, it is still a single task here. Different techniques doesn’t mean multiple tasks. Not so sure what single or multiple tasks matters here.