这个正则表达式如何找到素数? [英] How does this regex find primes?

问题描述

可能的重复:
如何判断一个数是否是素数正则表达式?

这个page 声称这个正则表达式发现了非质数(以及反例:质数):

This page claims that this regular expression discovers non-prime numbers (and by counter-example: primes):

/^1?$|^(11+?)\1+$/

这是如何找到素数的?

推荐答案

我觉得这篇文章解释得很好，但我也会尝试一下.

I think the article explains it rather well, but I'll try my hand at it as well.

输入采用一元形式.1 是 1，2 是 11，3 是 111，等等.零是一个空字符串.

Input is in unary form. 1 is 1, 2 is 11, 3 is 111, etc. Zero is an empty string.

正则表达式的第一部分将 0 和 1 匹配为非素数.第二个是魔法发挥作用的地方.

The first part of the regex matches 0 and 1 as non-prime. The second is where the magic kicks in.

(11+?) 从查找除数开始.它首先被定义为 11 或 2. \1 是一个变量，指的是先前捕获的匹配，所以 \1+ 确定是否该数字可被该除数整除.(111111首先将变量赋值给11，然后确定剩余的1111是11重复，所以6 可以被 2 整除.)

(11+?) starts by finding divisors. It starts by being defined as 11, or 2. \1 is a variable referring to that previously captured match, so \1+ determines if the number is divisible by that divisor. (111111 starts by assigning the variable to 11, and then determines that the remaining 1111 is 11 repeated, so 6 is divisible by 2.)

如果数字不能被二整除，正则表达式引擎会增加除数.(11+?) 变成 111，我们再试一次.如果正则表达式在任何时候匹配，则该数字有一个不产生余数的除数，因此该数字不能是质数.

If the number is not divisible by two, the regex engine increments the divisor. (11+?) becomes 111, and we try again. If at any point the regex matches, the number has a divisor that yields no remainder, and so the number cannot be prime.

这篇关于这个正则表达式如何找到素数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！