可以编写 Perl/Java/etc 正则表达式来匹配十进制（非）素数吗？
Can a Perl/Java/etc regular expression be written to match decimal (non-)prime numbers?
相关questions/material:
How can we match a^n b^n with Java regex?
How to determine if a number is a prime with regex?（处理 一元 素数匹配，而我正在寻找基数 ≥ 2；尽管如此，这是一个不错的技巧，还有什么让我考虑这个）
http://nikic.github.io/2012/06/15/The-true-power-of-regular-expressions.html
众所周知，各种编程语言支持的"regular expressions"生成的语言在形式意义上是非常规的，并且如上文material所示，能够识别至少一些 上下文相关语言。
语言 L = {x | x is a prime number in base 10} 是一种上下文相关的语言，因为素数可以通过线性有界自动机来测试（但它不是通过抽水引理参数进行的上下文无关语言）。
那么，是否可以编写一个 Perl 或 Java 正则表达式来准确接受所有以 10 为基数的素数？如果感觉更容易，请随意替换任何其他 ≥ 2 的基数或精确识别所有合数。
使用转义符，例如，运行 任意 Perl 代码被认为是作弊。重复替换（这很容易图灵完备）也不在范围内；整个工作应该在正则表达式中完成。这个问题更多的是关于正则表达式到底有多强大的边界。
注意：这些正则表达式是为 PHP 编写的，并使用在许多但不是所有语言中使用的所有格量词，例如 java-script 不支持它们。这也是非常低效的，很快就会变得不可行。
编辑：这里是 base 10 \b(((\d)(?=[\d\s]*({0,10}(n(?=.*n)|nn(?=.*1)|n{3}(?=.*2)|n{4}(?=.*3)|n{5}(?=.*4)|n{6}(?=.*5)|n{7}(?=.*6)|n{8}(?=.*7)|n{9}(?=.*8))?)))+)(?![\d\s]*(n(?=))++(..?1|(...*)+1)) 之后我使用 base 2 来简化事情。
编辑：这个将允许您传入一个包含多个二进制数的字符串并匹配那些是素数的字符串 \b(((\d)(?=[\d\s]*({0,2}n(?=.*)|{0,2})))+)(?![\d\s]*(n(?=))++(..?1|(...*)+1))
它基本上通过使用边界 \b 而不是字符串 ^ 的开头来做到这一点，它允许任意数量的小数和 spaces 向前移动到 ns 并将测试基数 1 表示的整个部分包装在 a消极的前瞻性。除此之外，它的工作方式与下面的相同。
例如 1111 1011 nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn1
将匹配 1011.
我设法找到了我认为可行的东西（检查到 25）并且它匹配非素数。这是以 2 为底数（更容易解释）^((\d)(?= \d*\s({0,2}n(?=.*)|{0,2})))+\s(n(?=))*+\K(..?1|(..+?)+1)这可以扩展到以 n 为底数，但这会非常快速地扩展正则表达式。为了让这个正则表达式工作，我需要一些额外条件（有点老套），输入字符串必须是数字后跟 space 后跟至少与你的数字值一样多的 n 个字符（如果你有你需要的数字 10 在它之后 leat 10 ns）然后是你的基数数字，不包括你的 0 数字（例如基数 10 123456789），不包括你的 0。例如 11 nnnnnnnnnnnnnn1。这是因为正则表达式没有可访问的存储空间，因此我需要使用捕获组来执行此操作。最后，此正则表达式使用 /x 忽略表达式中的 whitespaces，如果您不想使用它，则删除所有 space。
我现在将分 3 个步骤解释这是如何工作的。
此正则表达式分为 3 个部分：
Part 1:这部分将一个基数n>1改为基数1作为ns的捕获组
这是 ^((\d)(?= \d*\s({0,2}n(?=.*)|{0,2})))+ 的部分，它与问题中的 a^nb^n 示例非常相似。前面的 ^ 意味着完整的比赛必须从头开始，这对以后很重要。
此代码的主要结构是 ^((\d)(?= \d*\s (suff)))+ 这取开始和第一个 space 之间的每个小数，并使用 (\d)(?=) 执行正向前看，其中 \d 是小数， (?=) 是前瞻性的， \d 在捕获组 () 中供以后使用。这是我们目前正在查看的数字。
look-ahead 的内部实际上不是检查前面的条件，而是建立一个捕获组来表示我们在基数 1 中的数字。捕获组的内部如下所示
\d*\s({0,2}n(?=.*)|{0,2}))
\d*\s 部分基本上将我们正在查看的字符移动到剩余数字 \d* 的其余部分（\d 是数字，* 是 0 到 n 尽可能多的次数）现在剩下我们在看 ns 的开头。
({0,2}n(?=.*)|{0,2}))
是一个自引用捕获组，这里需要您放在末尾的数字。该组匹配自身 0 到 2 次，但尽可能多（使用 \3{0,2 } \3 表示第 3 组，{0,2} 表示从 0 到 2 次匹配）这意味着如果在当前数字之前有一个数字，则其基数 1 表示乘以 2。对于基数 10，这将是 10或 16 以 16 为基数。如果这是第一个数字，则该组将未定义，因此它将匹配 0 次。然后，它根据匹配我们当前正在处理的数字（使用其捕获组）添加单个 n 或不添加 n。它通过使用正向展望来查看我们放置数字的输入末尾来实现这一点，n(?=.*\2) 如果它可以找到我们正在处理的数字后面的任何内容，则它匹配 n。这允许它识别我们此时正在处理的数字。 （我本来想往后看，但它们是固定长度的）
如果你有基数 3 并且想检查你当前正在处理的数字是否为 2，你将使用 nn(?=.*1) 这将仅在数字为二时匹配 nn。我们使用了或运算符“|”对于所有这些，如果没有找到数字，我们假设它是 0 并且不添加 ns。因为这是在捕获组中，所以这个匹配被保存在组中。
在这部分的总结中，我们所做的是让每个数字向前看，取前面数字的基数 1 表示（保存在捕获组中）并将它乘以基数然后匹配它，然后添加到它基于数字的一种表示形式并将其保存在组中。如果您依次对每个数字执行此操作，您将获得该数字的基数表示形式。让我们看看例子。 101 nnnnnnnnnnnnnnnnnn1
首先是因为^才去sat。所以：101 nnnnnnnnnnnnnnnnnnn1
然后它转到第一个数字并将其保存在捕获摸索中101 nnnnnnnnnnnnnnnnn1
第 2 组：1
它使用 \d*\s 进行前瞻以超越所有数字和第一个 space。 101 nnnnnnnnnnnnnnnnn1
现在在捕获组 3 中
取这个caputing group之前的值匹配0到2次
因为未定义所以匹配0次。
现在再次向前看，试图找到与捕获组 2 中的数字相匹配的数字 101 nnnnnnnnnnnnnnnnn1
因为它被发现匹配捕获组 3 中的 1 n 101 nnnnnnnnnnnnnnnn1
它现在离开第 3 组，更新它的值并离开前瞻
第 3 组 = n
它现在查看下一个数字并将其保存在捕获组 101 nnnnnnnnnnnnnnnnn1
组 2 = 0
组 3 = n
然后它也使用前瞻并转到第一个 n 101 nnnnnnnnnnnnnnnnn1
然后匹配第 3 组 0 到 2 次，但尽可能多 n 101 nnnnnnnnnnnnnnnn1
然后它使用前瞻来尝试匹配第 2 组中的数字，它可以这样做，因此它不添加 ns，然后返回第 3 组和前瞻
group3 = nn
它现在查看下一个数字并将其保存在组 2 101 nnnnnnnnnnnnnnnnn1
使用前瞻，它进入 ns 的开头并匹配 2 次组 3 101 nnnnnnnnnnnnnnnnn1
然后它使用前瞻来尝试匹配第 2 组中的数字，它发现它匹配第 3 组和前瞻中的 n 和 returns。
第 3 组 = nnnnn
第 3 组现在包含我们数字的基数 1 表示。
第 2 部分 将 ns 减小到以 1 为基数表示您的数字的大小
\s(n(?=))*+\K
这匹配 space 然后匹配 ns 只要你能匹配前面的第 3 组（你的数字的基数表示）。它通过使用所有格的 *+ 尽可能多地匹配 n 来做到这一点（它永远不会放弃匹配，这是为了阻止匹配在以后被缩小以使匹配工作） n 具有积极的前瞻性 n (?=\3) 这意味着只要前面有组 3 就会匹配 n（\3 给出捕获组 3）。这给我们留下了以 1 为基数的表示形式，而数字是唯一不匹配的东西。然后我们用 \K 表示从这里重新开始匹配。
第三部分
我们现在使用问题中提到的相同算法来获取素数，除了我们强制它在表示基础的开始和数字的开始之间不匹配。您可以在此处阅读其工作原理 How to determine if a number is a prime with regex?
最后要将它变成一个 base n 正则表达式，你必须做一些事情
^((\d)(?= \d*\s({0,2}n(?=.*)|{0,2})))+\s(n(?=))*+\K(..?1|(..+?)+1)
首先在输入字符串的末尾添加更多数字，然后更改 n
?=.* to n?=.*n | n?=.*1 n?=.*3 .., n?=.***n**
最后把\3{0,2}改成\3{0,n}。其中 n 是基数。还要记住，如果没有正确的输入字符串，这将无法工作。
相关questions/material:
How can we match a^n b^n with Java regex?
How to determine if a number is a prime with regex?（处理 一元 素数匹配，而我正在寻找基数 ≥ 2；尽管如此，这是一个不错的技巧，还有什么让我考虑这个）
http://nikic.github.io/2012/06/15/The-true-power-of-regular-expressions.html
众所周知，各种编程语言支持的"regular expressions"生成的语言在形式意义上是非常规的，并且如上文material所示，能够识别至少一些 上下文相关语言。
语言 L = {x | x is a prime number in base 10} 是一种上下文相关的语言，因为素数可以通过线性有界自动机来测试（但它不是通过抽水引理参数进行的上下文无关语言）。
那么，是否可以编写一个 Perl 或 Java 正则表达式来准确接受所有以 10 为基数的素数？如果感觉更容易，请随意替换任何其他 ≥ 2 的基数或精确识别所有合数。
使用转义符，例如，运行 任意 Perl 代码被认为是作弊。重复替换（这很容易图灵完备）也不在范围内；整个工作应该在正则表达式中完成。这个问题更多的是关于正则表达式到底有多强大的边界。
注意：这些正则表达式是为 PHP 编写的，并使用在许多但不是所有语言中使用的所有格量词，例如 java-script 不支持它们。这也是非常低效的，很快就会变得不可行。
编辑：这里是 base 10 \b(((\d)(?=[\d\s]*({0,10}(n(?=.*n)|nn(?=.*1)|n{3}(?=.*2)|n{4}(?=.*3)|n{5}(?=.*4)|n{6}(?=.*5)|n{7}(?=.*6)|n{8}(?=.*7)|n{9}(?=.*8))?)))+)(?![\d\s]*(n(?=))++(..?1|(...*)+1)) 之后我使用 base 2 来简化事情。
编辑：这个将允许您传入一个包含多个二进制数的字符串并匹配那些是素数的字符串 \b(((\d)(?=[\d\s]*({0,2}n(?=.*)|{0,2})))+)(?![\d\s]*(n(?=))++(..?1|(...*)+1))
它基本上通过使用边界 \b 而不是字符串 ^ 的开头来做到这一点，它允许任意数量的小数和 spaces 向前移动到 ns 并将测试基数 1 表示的整个部分包装在 a消极的前瞻性。除此之外，它的工作方式与下面的相同。
例如 1111 1011 nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn1
将匹配 1011.
我设法找到了我认为可行的东西（检查到 25）并且它匹配非素数。这是以 2 为底数（更容易解释）^((\d)(?= \d*\s({0,2}n(?=.*)|{0,2})))+\s(n(?=))*+\K(..?1|(..+?)+1)这可以扩展到以 n 为底数，但这会非常快速地扩展正则表达式。为了让这个正则表达式工作，我需要一些额外条件（有点老套），输入字符串必须是数字后跟 space 后跟至少与你的数字值一样多的 n 个字符（如果你有你需要的数字 10 在它之后 leat 10 ns）然后是你的基数数字，不包括你的 0 数字（例如基数 10 123456789），不包括你的 0。例如 11 nnnnnnnnnnnnnn1。这是因为正则表达式没有可访问的存储空间，因此我需要使用捕获组来执行此操作。最后，此正则表达式使用 /x 忽略表达式中的 whitespaces，如果您不想使用它，则删除所有 space。
我现在将分 3 个步骤解释这是如何工作的。 此正则表达式分为 3 个部分：
Part 1:这部分将一个基数n>1改为基数1作为ns的捕获组
这是 ^((\d)(?= \d*\s({0,2}n(?=.*)|{0,2})))+ 的部分，它与问题中的 a^nb^n 示例非常相似。前面的 ^ 意味着完整的比赛必须从头开始，这对以后很重要。
此代码的主要结构是 ^((\d)(?= \d*\s (suff)))+ 这取开始和第一个 space 之间的每个小数，并使用 (\d)(?=) 执行正向前看，其中 \d 是小数， (?=) 是前瞻性的， \d 在捕获组 () 中供以后使用。这是我们目前正在查看的数字。
look-ahead 的内部实际上不是检查前面的条件，而是建立一个捕获组来表示我们在基数 1 中的数字。捕获组的内部如下所示
\d*\s({0,2}n(?=.*)|{0,2}))
\d*\s 部分基本上将我们正在查看的字符移动到剩余数字 \d* 的其余部分（\d 是数字，* 是 0 到 n 尽可能多的次数）现在剩下我们在看 ns 的开头。
({0,2}n(?=.*)|{0,2}))
是一个自引用捕获组，这里需要您放在末尾的数字。该组匹配自身 0 到 2 次，但尽可能多（使用 \3{0,2 } \3 表示第 3 组，{0,2} 表示从 0 到 2 次匹配）这意味着如果在当前数字之前有一个数字，则其基数 1 表示乘以 2。对于基数 10，这将是 10或 16 以 16 为基数。如果这是第一个数字，则该组将未定义，因此它将匹配 0 次。然后，它根据匹配我们当前正在处理的数字（使用其捕获组）添加单个 n 或不添加 n。它通过使用正向展望来查看我们放置数字的输入末尾来实现这一点，n(?=.*\2) 如果它可以找到我们正在处理的数字后面的任何内容，则它匹配 n。这允许它识别我们此时正在处理的数字。 （我本来想往后看，但它们是固定长度的） 如果你有基数 3 并且想检查你当前正在处理的数字是否为 2，你将使用 nn(?=.*1) 这将仅在数字为二时匹配 nn。我们使用了或运算符“|”对于所有这些，如果没有找到数字，我们假设它是 0 并且不添加 ns。因为这是在捕获组中，所以这个匹配被保存在组中。
在这部分的总结中，我们所做的是让每个数字向前看，取前面数字的基数 1 表示（保存在捕获组中）并将它乘以基数然后匹配它，然后添加到它基于数字的一种表示形式并将其保存在组中。如果您依次对每个数字执行此操作，您将获得该数字的基数表示形式。让我们看看例子。 101 nnnnnnnnnnnnnnnnnn1
首先是因为^才去sat。所以：101 nnnnnnnnnnnnnnnnnnn1
然后它转到第一个数字并将其保存在捕获摸索中101 nnnnnnnnnnnnnnnnn1
第 2 组：1
它使用 \d*\s 进行前瞻以超越所有数字和第一个 space。 101 nnnnnnnnnnnnnnnnn1
现在在捕获组 3 中
取这个caputing group之前的值匹配0到2次
因为未定义所以匹配0次。
现在再次向前看，试图找到与捕获组 2 中的数字相匹配的数字 101 nnnnnnnnnnnnnnnnn1
因为它被发现匹配捕获组 3 中的 1 n 101 nnnnnnnnnnnnnnnn1
它现在离开第 3 组，更新它的值并离开前瞻 第 3 组 = n
它现在查看下一个数字并将其保存在捕获组 101 nnnnnnnnnnnnnnnnn1
组 2 = 0
组 3 = n
然后它也使用前瞻并转到第一个 n 101 nnnnnnnnnnnnnnnnn1
然后匹配第 3 组 0 到 2 次，但尽可能多 n 101 nnnnnnnnnnnnnnnn1
然后它使用前瞻来尝试匹配第 2 组中的数字，它可以这样做，因此它不添加 ns，然后返回第 3 组和前瞻
group3 = nn
它现在查看下一个数字并将其保存在组 2 101 nnnnnnnnnnnnnnnnn1 使用前瞻，它进入 ns 的开头并匹配 2 次组 3 101 nnnnnnnnnnnnnnnnn1 然后它使用前瞻来尝试匹配第 2 组中的数字，它发现它匹配第 3 组和前瞻中的 n 和 returns。 第 3 组 = nnnnn 第 3 组现在包含我们数字的基数 1 表示。
第 2 部分 将 ns 减小到以 1 为基数表示您的数字的大小
\s(n(?=))*+\K
这匹配 space 然后匹配 ns 只要你能匹配前面的第 3 组（你的数字的基数表示）。它通过使用所有格的 *+ 尽可能多地匹配 n 来做到这一点（它永远不会放弃匹配，这是为了阻止匹配在以后被缩小以使匹配工作） n 具有积极的前瞻性 n (?=\3) 这意味着只要前面有组 3 就会匹配 n（\3 给出捕获组 3）。这给我们留下了以 1 为基数的表示形式，而数字是唯一不匹配的东西。然后我们用 \K 表示从这里重新开始匹配。
第三部分 我们现在使用问题中提到的相同算法来获取素数，除了我们强制它在表示基础的开始和数字的开始之间不匹配。您可以在此处阅读其工作原理 How to determine if a number is a prime with regex?
最后要将它变成一个 base n 正则表达式，你必须做一些事情
^((\d)(?= \d*\s({0,2}n(?=.*)|{0,2})))+\s(n(?=))*+\K(..?1|(..+?)+1)
首先在输入字符串的末尾添加更多数字，然后更改 n
?=.* to n?=.*n | n?=.*1 n?=.*3 .., n?=.***n**
最后把\3{0,2}改成\3{0,n}。其中 n 是基数。还要记住，如果没有正确的输入字符串，这将无法工作。