Arcane是Java中的Prime方法 [英] Arcane isPrime method in Java

问题描述

考虑以下方法：

public static boolean isPrime(int n) {
    return ! (new String(new char[n])).matches(".?|(..+?)\\1+");
}

我从未成为正规表达大师，所以任何人都可以完全解释如何这个方法真的有效吗？ 此外，与确定整数是否为素数的其他可能方法相比是否有效？

I've never been a regular expression guru, so can anyone fully explain how this method actually works? Furthermore, is it efficient compared to other possible methods for determining whether an integer is prime?

推荐答案

首先，请注意此正则表达式适用于一元计数系统中表示的数字，即

First, note that this regex applies to numbers represented in a unary counting system, i.e.

1       is 1
11      is 2
111     is 3
1111    is 4
11111   is 5
111111  is 6
1111111 is 7

依此类推。真的，可以使用任何字符（因此表达式中的。 s），但我会使用1。

and so on. Really, any character can be used (hence the .s in the expression), but I'll use "1".

其次，请注意此正则表达式匹配复合（非素数）数字;因此否定检测到素数。

Second, note that this regex matches composite (non-prime) numbers; thus negation detects primality.

说明：

表达式的前半部分，

.?

表示字符串（0）和1（1）是匹配的，即不是主要（根据定义，虽然有争议。）

says that the strings "" (0) and "1" (1) are matches, i.e. not prime (by definition, though arguable.)

下半部用简单的英文说：

The second half, in simple English, says:

匹配长度最短的字符串至少2，例如，11（2）。现在，看看我们是否可以通过重复它来匹配整个字符串。 1111（4）匹配吗？ 111111（6）是否匹配？ 11111111（8）是否匹配？等等。如果没有，则再次尝试下一个最短的字符串111（3）。等等。

Match the shortest string whose length is at least 2, for example, "11" (2). Now, see if we can match the entire string by repeating it. Does "1111" (4) match? Does "111111" (6) match? Does "11111111" (8) match? And so on. If not, then try it again for the next shortest string, "111" (3). Etc.

现在，如果原始字符串无法与多个匹配，您现在可以看到它的子串，然后根据定义，它是素数！

You can now see how, if the original string can't be matched as a multiple of its substrings, then by definition, it's prime!

BTW，非贪婪的运算符？是什么使得算法从最短的开始计数。

BTW, the non-greedy operator ? is what makes the "algorithm" start from the shortest and count up.

效率：

这很有趣，但肯定没有效率，各种论点，其中一些我将在下面合并：

It's interesting, but certainly not efficient, by various arguments, some of which I'll consolidate below:

• 正如@TeddHopp指出的那样，众所周知的Eratosthenes筛选方法不会费心去检查4,6和9的整数倍，在检查倍数时已经访问过了唉，这种正则表达式方法穷尽地检查每个较小的整数。

• As @TeddHopp notes, the well-known sieve-of-Eratosthenes approach would not bother to check multiples of integers such as 4, 6, and 9, having been "visited" already while checking multiples of 2 and 3. Alas, this regex approach exhaustively checks every smaller integer.

正如@PetarMinchev所说，我们可以短路多次检查方案一旦我们达到数字的平方根。我们应该能够因为一个因子更大而不是平方根必须与一个因子较小比平方根合作（因为否则两个因子大于平方根会产生一个产品大于数字），如果存在这个更大的因素，那么我们应该已经遇到（因此匹配）较小的因素。

As @PetarMinchev notes, we can "short-circuit" the multiples-checking scheme once we reach the square root of the number. We should be able to because a factor greater than the square root must partner with a factor lesser than the square root (since otherwise two factors greater than the square root would produce a product greater than the number), and if this greater factor exists, then we should have already encountered (and thus, matched) the lesser factor.

As @ Jesper和@Brian简明扼要地说，从非算法的角度来看，考虑正则表达式如何通过分配内存来存储字符串，例如 char [9000] for 9000.嗯，这很容易，不是吗？ ;）

As @Jesper and @Brian note with concision, from a non-algorithmic perspective, consider how a regular expression would begin by allocating memory to store the string, e.g. char[9000] for 9000. Well, that was easy, wasn't it? ;)

正如@Foon所说，存在概率方法，对于较大的数字可能更有效，尽管它们可能并不总是正确的（改为伪造的）。但也有确定性测试，它们比基于筛选的方法100％准确且效率更高。 Wolfram 有一个很好的总结。

As @Foon notes, there exist probabilistic methods which may be more efficient for larger numbers, though they may not always be correct (turning up pseudoprimes instead). But also there are deterministic tests that are 100% accurate and far more efficient than sieve-based methods. Wolfram's has a nice summary.

这篇关于Arcane是Java中的Prime方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！