Arcane是Java中的Prime方法

Question

请考虑以下方法:

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

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

Answer 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).等等.

你现在可以看到,如果原始字符串不能作为其子串的倍数匹配,那么根据定义,它是如此!

顺便说一句,非贪婪的运算符?是使"算法"从最短的开始并计数的原因.

效率:

有趣的,但肯定没有效率,各种论点,其中一些我将在下面巩固:

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

• 正如@PetarMinchev指出的那样,一旦达到数字的平方根,我们就可以"短路"多次检查方案.我们应该能够因为一个因素更大的比一个因素平方根必备伴侣较少比的平方根(因为并非平方根更大的两个因素会产生产品的数量比越大),如果这更大的因素存在,那么我们应该已经遇到(因而匹配)较小的因素.

• 正如@Jesper和@Brian所说,从非算法的角度来看,考虑如何通过分配内存来存储字符串来开始正则表达式,例如 char[9000] 9000.嗯,这很容易,不是吗？;)

• 正如@Foon所指出的那样,存在概率方法,这些方法对于较大的数字可能更有效,尽管它们可能并不总是正确的(改为伪随机).但也存在确定性测试,这些测试100%准确并且比基于筛选的方法更有效.Wolfram有一个很好的总结.

Answer 2

素数的一元特征及其工作原理已经涵盖.所以这是使用传统方法和这种方法的测试:

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毫秒).