在Python中使用正则表达式编写的is_prime函数（来自Perl）

Question

在Python中使用正则表达式编写的is_prime函数（来自Perl）

9

我已经阅读了这篇文章, 文章中使用了/^1?$|^(11+?)\1+$/ Perl 正则表达式来测试一个数是否为质数。

过程：

s = '1' * your_number

如果字符串符合正则表达式，则它不是质数。如果不符合，则是质数。

你如何将该正则表达式翻译成Python的re模块？

- Juanjo Conti

14

刚当我以为我见过所有事情的时候…… - Mike DeSimone

一个更紧凑的素数测试在这里 https://dev59.com/6HI-5IYBdhLWcg3wiY3a all(i%d for d in range(2,i)) - John La Rooy

3

正则表达式匹配中的回溯引用是NP难问题：http://perl.plover.com/NPC/ - Greg Bacon

1

请参见http://www.perlmonks.org/?node_id=21580和http://web.archive.org/web/20010508215502/http://www.foad.org/~abigail/Perl/Talks/Japhs/primes.html。 - Sinan Ünür

1

哦，天啊...那太疯狂了，但也很令人印象深刻。 - MikeyB

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- interjay · Accepted Answer

它可以直接使用（除了前后没有斜杠，在Python中不需要它们）：

pattern = r'^1?$|^(11+?)\1+$'
re.match(pattern, '1'*10)    #matches
re.match(pattern, '1'*11)    #doesn't match

这里需要的唯一非标准正则表达式功能是反向引用（\1），这在Perl和Python中都得到支持。