[java] 숫자가 정규 표현식의 소수인지 확인하는 방법은 무엇입니까?

주어진 다음 정규식 : 나는 소수성 테스트의 정규식 부분 밖에 설명 할 것이다 String s반복으로 구성 String t, 발견을 t.

    System.out.println(
        "MamamiaMamamiaMamamia".replaceAll("^(.*)\\1+$", "$1")
    ); // prints "Mamamia"

작동 방법은 정규식 캡처입니다 (.*)에 \1, 다음이 있다면보고 \1+를 다음과 같습니다. 은 Using ^및 $보장하지만이 경기는 전체 문자열이어야.

그래서 어떤 식으로 우리 String s는의 “다수”인을 부여 받았으며 String t정규 표현식은 그런 것을 찾을 것입니다 t(가장 \1욕심이 많기 때문에 가능한 가장 길다 ).

이 정규식이 왜 작동하는지 이해하고 나면 우선 OP 테스트의 첫 번째 대안을 무시하고 우선 순위 테스트에 사용되는 방법을 간단하게 설명합니다.

• 의 우선도를 테스트하려면 n먼저 String길이를 생성 n하십시오 (같은 것으로 채워짐 char)
• 정규식 캡처는 String약간의 길이 (말의 k에) \1, 그리고 시도 일치하는 \1+의 나머지String
  • 일치하는 경우 n의 적절한 배수 k이며 따라서 n소수가 아닙니다.
  • 일치가 없습니다 경우, 그러한은 k그 분할을 존재하지 않는 n, 그리고 n따라서 소수

.?|(..+?)\1+소수 는 어떻게 일치합니까?

실제로는 그렇지 않습니다! 그것은 일치 String 길이가 NOT 소수!

• .?: String길이 의 대체 일치 의 첫 번째 부분 0또는 1(정의에 의한 소수는 아님)
• (..+?)\1+: 대체의 두 번째 부분, 위에서 설명한 정규 표현식의 변형은 String길이의 n“배” String길이 k >= 2(즉 n소수가 아닌 복합) 의 길이 와 일치 합니다.
  • reluctant 수정자는 ?실제로 정확성을 위해 필요하지는 않지만 더 작은 것을 k먼저 시도하여 프로세스 속도를 높이는 데 도움이 될 수 있습니다

명령문 의 ! boolean보수 연산자에 유의하십시오 . 정규식이 일치 하지 않을 때가 가장 중요합니다! 이중 음의 논리이므로 혼란 스럽습니다.returnmatchesn

단순화

다음은 코드를보다 읽기 쉽게 작성하기 위해 다시 작성하는 것입니다.

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

위의 내용은 원래 Java 코드와 본질적으로 동일하지만 논리를 이해하기 쉽도록 로컬 변수에 할당 된 여러 명령문으로 나뉩니다.

다음과 같이 유한 반복을 사용하여 정규식을 단순화 할 수도 있습니다.

boolean isNotPrimeN = lengthN.matches(".{0,1}|(.{2,})\\1+");

또, 소정의 String길이를 n동일 가득 char,

• .{0,1}n = 0,1소수 가 아닌지 확인
• (.{2,})\1+소수가 아닌 n적절한 배수 인지 확인합니다.k >= 2

꺼리는 수정자를 ?설정 한 것을 제외 하고 \1(명확성을 위해 생략) 위의 정규식은 원본과 동일합니다.

더 재미있는 정규식

다음 정규식은 비슷한 기술을 사용합니다. 교육적이어야합니다.

System.out.println(
    "OhMyGod=MyMyMyOhGodOhGodOhGod"
        .replaceAll("^(.+)(.+)(.+)=(\\1|\\2|\\3)+$", "$1! $2! $3!")
); // prints "Oh! My! God!"

또한보십시오

• 정규식 : 탐욕스러운 사람

답변

/^1?$|^(11+?)\1+$/