Arcane是Java中的Prime方法
考虑以下方法：
public static boolean isPrime(int n) { return ! (new String(new char[n])).matches(".?|(..+?)\\1+"); } 我从来没有成为正规表达大师，所以任何人都可以完全解释这种方法是如何运作的吗？ 此外 ，与确定整数是否为素数的其他可能方法相比，它是否有效？
首先，请注意，此正则表达式适用于一元计数系统中表示的数字，即
1 is 1 11 is 2 111 is 3 1111 is 4 11111 is 5 111111 is 6 1111111 is 7
等等。 实际上，可以使用任何字符（因此表达式中的.s），但我会使用“1”。
其次，请注意此正则表达式匹配复合 （非素数）数字; 因此否定检测到素性。
说明：
表达的前半部分，
.?
说字符串“”（0）和“1”（1）是匹配的， 即不是素数 （根据定义， 虽然可论证） 。
下半场用简单的英文说：
匹配长度至少为2的最短字符串，例如“11”（2）。 现在，看看我们是否可以通过重复它来匹配整个字符串。 “1111”（4）匹配吗？ “111111”（6）是否匹配？ “11111111”（8）是否匹配？ 等等。 如果没有，则再次尝试下一个最短的字符串“111”（3）。 等等。
你现在可以看到，如果原始字符串不能作为其子串的倍数匹配，那么根据定义，它是如此！
BTW，非贪婪的运营商? 是什么让“算法”从最短的开始计数。
效率：
有趣的，但肯定没有效率，各种论点，其中一些我将在下面巩固：
-
正如@TeddHopp指出的那样，众所周知的Eratosthenes筛选方法不会费心去检查4,6和9的整数倍，在检查2和3的倍数时已经“访问过”。唉，这个正则表达式方法详尽地检查每个较小的整数。
-
正如@PetarMinchev所指出的那样，一旦达到数字的平方根，我们就可以将多重检查方案“短路”。 我们应该能够因为大于平方根的因子必须与一个小于平方根的因子合作（因为否则大于平方根的两个因子会产生大于该数的乘积），如果存在这个更大的因子，那么我们应该已经遇到（并因此匹配）较小的因素。
-
正如@Jesper和@Brian所说，从非算法的角度来看，考虑如何通过分配内存来存储字符串来开始正则表达式， 例如
char[9000]为9000.嗯，这很容易，不是吗？ ;） -
正如@Foon所指出的那样，存在概率方法，对于较大的数字可能更有效，尽管它们可能并不总是正确的（改为伪随机）。 但也存在确定性测试，这些测试100％准确并且比基于筛选的方法更有效。 Wolfram有一个很好的总结。
素数的一元特征及其工作原理已经涵盖。 所以这是使用传统方法和这种方法的测试：
public class Main { public static void main(String[] args) { long time = System.nanoTime(); for (int i = 2; i < 10000; i++) { isPrimeOld(i); } time = System.nanoTime() - time; System.out.println(time + " ns (" + time / 1000000 + " ms)"); time = System.nanoTime(); for (int i = 2; i < 10000; i++) { isPrimeRegex(i); } time = System.nanoTime() - time; System.out.println(time + " ns (" + time / 1000000 + " ms)"); System.out.println("Done"); } public static boolean isPrimeRegex(int n) { return !(new String(new char[n])).matches(".?|(..+?)\\1+"); } public static boolean isPrimeOld(int n) { if (n == 2) return true; if (n < 2) return false; if ((n & 1) == 0) return false; int limit = (int) Math.round(Math.sqrt(n)); for (int i = 3; i <= limit; i += 2) { if (n % i == 0) return false; } return true; } }
此测试计算从2开始，数字是否为9,999以上。这是在相对强大的服务器上的输出：
8537795 ns (8 ms) 30842526146 ns (30842 ms) Done
因此，一旦数字变得足够大，它就非常低效。 （对于高达999，正则表达式在大约400毫秒内运行。）对于小数字，它速度很快，但是以常规方式生成高达9,999的素数仍然比以前生成高达99的素数更快（ 23毫秒）。
这不是检查数字是否为素数的真正有效方法（它检查每个除数）。
一种有效的方法是检查最高为sqrt(number)除数。 如果你想确定一个数字是否是素数，那就是这样。 否则有概率素数检查更快，但不是100％正确。