정규식을 사용하여 소수인지 확인하는 방법

정규식을 사용하여 소수인지 확인하는 방법

RosettaCode에서 Java의 다음 코드 예를 찾았습니다.

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

• 자바에 대해서는 잘 모르지만 regex 자체를 제외한 이 스니펫의 모든 측면을 이해하고 있습니다.
• 내장된 PHP 함수에서 찾을 수 있는 Regex에 대한 기본에서 기본까지 고급 지식을 가지고 있습니다.

어떻게요?.?|(..+?)\\1+소수점 일치?

이 부분을 이해한다고 하셨는데, 강조하기 위해 생성된 String의 길이는 제공된 숫자와 동일합니다.따라서 문자열에는 3개의 문자가 포함되어 있습니다.n == 3.

.?

정규식의 첫 번째 부분은 "0번 또는 1번"이라고 합니다.그럼 기본적으로 0자 또는 1자입니까?아니면 위에서 말씀드린 바와 같이n == 0 || n == 1만약 성냥이 있다면, 부정을 돌려주세요.이것은 0과 1이 소수가 아니라는 사실과 일치한다.

(..+?)\\1+

정규식의 두 번째 부분은 그룹 및 배경 참조에 의존하여 조금 더 까다롭습니다.그룹은 괄호 안의 임의의 것으로 나중에 사용할 수 있도록 regex 엔진에 의해 캡처되어 저장됩니다.백레퍼런스는 나중에 같은 regex에서 사용되는 일치된 그룹입니다.

그룹은 1개의 문자를 캡처한 후 1개 이상의 문자를 캡처합니다.(+ 문자는 하나 또는 여러 개의 이전 문자 또는 그룹만 의미합니다.그러니까 '두 글자, 네 글자, 여섯 글자 등'이 아니라 '두 글자, 세 글자 등'입니다.+?는 +와 비슷하지만 가능한 한 적은 글자를 조합하려고 합니다.+는 보통 가능하면 문자열 전체를 게걸스럽게 먹으려고 합니다.이 경우 백레퍼런스 부분이 작동하지 않기 때문입니다.)

다음 부분은 백레퍼런스입니다.같은 문자 세트(2개 이상)가 다시 표시됩니다.백 레퍼런스가 한 번 이상 나타납니다.

따라서 캡처된 그룹은 캡처된 자연 수(2자 이상)에 해당합니다.그런 다음 해당 그룹이 자연스럽게 몇 번(2회 이후) 나타납니다.일치하는 것이 있는 경우, 이는 n-length 문자열과 일치하는 2개 이상의 숫자의 곱을 찾을 수 있음을 의미합니다.즉, 합성 n이 있습니다.다시, 성공한 일치의 부정을 반환합니다.n은 소수가 아닙니다.

일치하는 것을 찾을 수 없으면 2보다 크거나 같은 두 자연수의 곱을 구할 수 없습니다.또한 불일치와 프라임이 모두 있으므로 다시 일치 결과가 부정됩니다.

이제 보이시나요?믿을 수 없을 정도로 까다롭지만(그리고 계산도 비싸다!), 일단 손에 넣으면, 동시에 꽤 심플합니다. :- )

regex 파싱이 실제로 어떻게 작동하는지와 같은 추가 질문이 있으면 자세히 설명해 드릴 수 있습니다.하지만 지금은 이 답을 단순하게 유지하려고 합니다(또는 가능한 한 단순하게).

primality 테스트 이외의 regex 부분에 대해 설명하겠습니다.다음 regex가 주어진 경우String s반복으로 구성되다String t,찾는다t.

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

작동 방식은 정규식이 캡처하는 것입니다.(.*)안으로\1그 후, 그 다음,\1+그 뒤를 쫓고 있다.사용방법^그리고.$그럼 스트링 전체가 일치해야 합니다.

그래서 어떤 면에서는,String s이것은, 의 「상대」입니다.String tregex는 다음과 같이 검출됩니다.t(이후로 가능한 가장 긴 시간)\1욕심이 많다).

이 regex가 작동하는 이유를 이해한 후에는 (현재로서는 OP regex의 첫 번째 대체를 무시함) primality 테스트에 사용되는 방법을 간단히 설명합니다.

• primity를 테스트하려면n, 먼저 생성한다.String길쭉한n(같은 것으로 채워짐)char)
• regex가 캡처하는 것은String어느 정도 길이의 (예를 들어)k)을(를) 로\1일치하려고 합니다.\1+나머지 부분까지String
  • 일치하는 것이 있으면n의 적절한 배수이다.k, 따라서n프라임이 아닙니다.
  • 일치하는 것이 없으면, 그런 것도 없다.k분열하는 존재n,그리고.n그러므로 소수이다.

---

어떻게요?.?|(..+?)\1+소수점 일치?

사실 그렇지 않아요!일치합니다 String길이가 프라임이 아닙니다!

• .?: 대안의 첫 번째 부분이 일치합니다.String길쭉한0또는1(정의상 프라임이 아님)
• (..+?)\1+: 위에서 설명한 regex의 변형인 두 번째 교대 부분이 일치합니다.String길쭉한n의 '배수'입니다.String길쭉한k >= 2(즉,n소수가 아닌 합성물)입니다.
  • 꺼림칙한 수식어는?실제로는 정확성을 위해 필요하지 않지만, 더 작게 시도함으로써 프로세스의 속도를 높일 수 있습니다.k첫번째

주의:! boolean의 보완 연산자return스테이트먼트: 이 명령어는matches정규식이 일치하지 않을 때,n프라임!이중 부정 논리니까 헷갈릴 만도 하지!!

---

심플화

다음은 읽기 쉽게 하기 위해 코드를 간단히 고쳐 쓰는 방법입니다.

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(명확하게 하기 위해 추가), 위의 정규식은 원본과 동일합니다.

---

보다 즐거운 정규식

다음 regex는 유사한 기술을 사용하므로 교육적이어야 합니다.

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

「 」를 참조해 주세요.

• 정규 표현: 누가 더 욕심이 많은가

훌륭한 정규식 트릭(매우 비효율적이지만)...:)

regex는 다음과 같이 비소수를 정의합니다.

N <=1 OR N이 일부 K>1로 나누어지는 경우에만 N은 소수가 아니다.

N의 단순한 디지털 표현을 정규식 엔진에 전달하는 대신 반복 문자로 구성된 길이 N의 시퀀스를 공급한다.분리의 첫 번째 부분은 N=0 또는 N=1을 확인하고 두 번째 부분은 백레퍼런스를 사용하여 제수 K>1을 찾습니다.이것에 의해, regex 엔진은, 적어도 2회 반복할 수 있는 비어 있지 않은 서브 시퀀스를 검출해, 시퀀스를 형성합니다.이러한 수열이 존재한다면, 그 길이가 N을 나눈다는 것을 의미하므로, N은 소수가 아니다.

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

기준 1로 변환한 후의 숫자에 적용한다(1=1, 2=11, 3=120, ...).소수점 이외는 여기에 일치합니다.일치하지 않으면 프라임입니다.

여기에 설명이 있습니다.

언급URL : https://stackoverflow.com/questions/2795065/how-to-determine-if-a-number-is-a-prime-with-regex