Java中的Arcane isPrime方法

发布时间：2020-12-14 16:40:56 所属栏目：Java 来源：网络整理

导读：请考虑以下方法： public static boolean isPrime(int n) { return ! (new String(new char[n])).matches(".?|(..+?)1+");} 我从来不是一个正式的表达大师,所以任何人都可以完全解释这种方法实际上如何工作？此外,与确定整数是素数的其他可能方法相比,是否

请考虑以下方法：

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
22222   is 5
222221  is 6
2222211 is 7

等等.真的,可以使用任何字符(因此在表达式中使用.s),但是我将使用“1”.

其次,这个正则表达式匹配复合(非素数)数字;因此否定检测原色.

说明：

上半年的表达,

.?

说,字符串“”(0)和“1”(1)是匹配,即不是素数(根据定义,though arguable)

下半年简单的英文说：

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 “222221” (6) match? Does “22222111” (8) match? And so on. If not,then try it again for the next shortest string,“111” (3). Etc.

现在,您可以看到如果原始字符串不能匹配它的子字符串的倍数,那么根据定义,它是主要的！

BTW,非贪婪运算符？是什么使“算法”从最短的开始计数.

效率：

这很有趣,但肯定不是有效的,有各种各样的论据,其中一些将在下面整合：

>正如@TeddHopp所指出的那样,众所周知的Eratosthenes筛选方法不需要检查已经“检查”的4,6和9个整数的倍数,同时检查2和3的倍数.唉,这个正则表达式彻底检查每个较小的整数.
>正如@PetarMinchev所说,一旦我们达到数字的平方根,我们就可以“短路”多重检查方案.我们应该能够因为大于平方根的因子必须与小于平方根的因子相配合(因为否则两个大于平方根的因子会产生大于数的产物),如果这个更大的因子存在,那么我们应该已经遇到了(因此匹配)较小的因素.
作为@Jesper和@Brian注释,从非算法角度来说,考虑如何通过分配内存来存储字符串来开始正则表达式. char [9000]为9000.那很简单,不是吗？

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!