News for hackers. Stuff that matters.
Re:A regular expression to check for prime numbers (2007) by TrianguloY on Saturday March 05, 2022 @03:04AM (#30565461)
The regexp basically tests all dividers of the number (from 2 to the number-1), if it founds one, it says false and stops, if nothing is found, it says true.

101 is prime, but it does "only" a hundred checks approx.

7673121 is divisible by 3, so as soon as it tries to match groups of 3 it succeeds and stops.

767423 is prime, so it needs to do hundreds of millions of checks, that's probably why it hungs.

Basically: the runtime of the algorithm should be equivalent to the minimum divisor excluding 1 of the number.

There are no comments on this comment yet.