Check Prime Number

Q: 숫자가 소수인지 확인하는 시간 복잡도는 얼마인가요?

√n 까지의 시험 나눗셈은 O(√n) 시간과 O(1) 공간이 걸립니다. n 이 2^31-1 까지라면 최대 약 46,000 번 나누면 되며, 짝수 제수를 건너뛰면 23,000 번입니다. n-1 까지 모든 제수를 시험하는 방법은 O(n) 이며, 가장 큰 입력에서는 약 20억 단계가 걸립니다.

Q: 왜 n의 제곱근까지만 약수를 확인하나요?

약수는 곱이 n 인 쌍 d 와 n / d 로 나타납니다. 두 수가 모두 √n 보다 크다면 그 곱은 n 보다 커집니다. 따라서 모든 쌍에는 √n 이하인 수가 하나 있고, 그때까지 약수가 나타나지 않으면 n 은 소수입니다.

Q: 1은 소수인가요?

아니요. 소수는 정확히 두 개의 서로 다른 약수인 1 과 자기 자신을 가지며, 1 은 약수가 하나뿐입니다. 1 을 제외하면 모든 양의 정수의 소인수분해가 유일하게 유지됩니다. 그래서 isPrime(1) 은 false 를 반환합니다.

입문수학과 시뮬레이션

+10

소수는 1보다 큰 정수로, 약수가 1과 자기 자신뿐입니다. 양의 정수 n이 주어집니다. n이 소수이면 true를 반환하고, 그렇지 않으면 false를 반환하세요. 숫자 1은 소수가 아닙니다.

함수

isPrime(n: integer) → boolean

ninteger: 테스트할 양의 정수
반환값boolean: n이 소수이면 true, 그렇지 않으면 false

제약 조건

1 ≤ n ≤ 2³¹ - 1

예제

입력: n = 29
출력: true
설명: 2, 3, 4, 5 중 어느 것도 29를 나누지 않으며, 6 × 6 = 36은 이미 29를 넘었으므로 더 이상 찾을 약수가 없습니다. 29는 소수입니다.

입력: n = 1
출력: false
설명: 소수는 약수가 정확히 두 개이며, 1과 자기 자신입니다. 1은 약수가 하나뿐이므로 답은 false입니다.

입력: n = 91
출력: false
설명: 91은 소수처럼 보이지만, 7 × 13 = 91입니다. 나눗셈 인수 7은 탐색이 √91 ≈ 9.5를 지나기 전에 나타납니다.

후속 질문

3보다 큰 모든 소수는 6k-1 또는 6k+1 형태입니다. 이를 이용해 후보 약수의 3분의 1만 테스트할 수 있을까요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

정의에 따르면 2부터 n-1까지의 모든 약수가 아닌지 확인해야 하며, 가장 큰 소수 입력의 경우 나눗셈이 20억 번을 넘습니다. 약수는 곱해서 n이 되는 쌍으로 나타나며, 각 쌍에서 더 작은 수는 √n 이하입니다. 따라서 √n까지만 탐색하면 되며, 홀수 후보는 최대 약 23,000개입니다.

모든 약수를 시도해 보세요

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

정의가 알고리즘을 알려 줍니다. n ≥ 2인 수는 2, 3, ..., n-1 중 어느 것도 그 수를 나누지 않을 때 소수입니다. 각 후보 d에 대해 n % d == 0인지 검사하고, 나누어떨어지는 첫 번째 후보에서 false를 반환합니다. 91의 경우 반복문은 2부터 6까지 시도한 뒤 7에서 멈춥니다.

먼저 n < 2인 경우를 처리하세요. n = 1이면 후보 범위가 비어 있으므로, 반복문은 약수를 찾지 못하고 1을 소수라고 판단하게 됩니다.

합성수는 보통 일찍 멈추지만, 소수는 모든 검사를 통과하므로 반복문은 끝까지 실행됩니다. 소수인 n = 2147483647의 경우 약 2.1 × 10^9번의 나눗셈을 수행해야 하며, 이는 몇 초 안에 허용되는 횟수를 훨씬 넘습니다.

알고리즘

n < 2이면 false를 반환합니다.
d를 2부터 n-1까지 반복합니다.
n % d == 0이면 false를 반환합니다.
반복문이 끝난 후 true를 반환합니다.

def isPrime(n):
    if n < 2:
        return False
    for d in range(2, n):
        if n % d == 0:
            return False
    return True

제곱근까지의 시행 나눗셈

핵심 아이디어

약수는 쌍으로 나타납니다. d가 n을 나누면 n / d도 나누며, 두 수를 곱하면 n이 됩니다. 두 수가 모두 √n보다 클 수는 없습니다. 그러면 곱이 n보다 커지기 때문입니다. 따라서 n에 1과 자기 자신 이외의 약수가 있다면, 그중 하나는 √n 이하입니다. 91의 경우 약수 쌍은 7과 13이고, 7 ≤ 9.5입니다. √n 이하의 수 중 n을 나누는 수가 없다면 그보다 큰 수 중에도 없습니다.

제곱근 함수를 호출하는 대신 상한을 d * d ≤ n으로 표현하세요. 이렇게 하면 반올림 없이 정수로 계산됩니다. 등호도 중요합니다. 49 = 7 × 7이고, 유일한 약수 7은 정확히 √49에 있습니다.

후보의 절반을 건너뛸 수도 있습니다. 2는 별도로 처리하세요. 짝수 n은 2일 때만 소수입니다. 그 후 홀수 n에는 홀수 약수만 있으므로 3에서 시작해 2씩 증가하면 됩니다. n = 2147483647의 경우 이제 반복문은 2.1 × 10^9번이 아니라 약 23,000번 실행됩니다.

알고리즘

n < 2이면 false를 반환합니다.
n이 짝수이면 n == 2인지 여부를 반환합니다.
d를 3으로 시작하고, d에 64비트 유형을 사용하여 d * d ≤ n인 동안 반복합니다.
n % d == 0이면 false를 반환합니다. 그렇지 않으면 d에 2를 더합니다.
반복문이 끝난 후 true를 반환합니다.

def isPrime(n):
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2  # 2 is the only even prime
    d = 3
    while d * d <= n:
        if n % d == 0:
            return False
        d += 2
    return True

함정과 경계 사례

핵심 아이디어는 한 줄이면 충분합니다. 버그는 경계값, 즉 가장 작은 입력과 마지막 약수에서 발생합니다.

1에 대해 true를 반환하는 경우. 약수가 두 개가 아니라 하나이므로 소수가 아닙니다.
2가 짝수라는 이유로 제외하는 경우. 짝수를 제외하기 전에 n == 2인지 확인하세요.
≤ 대신 d * d < n인 동안 반복하는 경우. 그러면 9, 49, 2147117569 = 46337²와 같은 소수의 제곱이 소수로 판정됩니다.
d * d에서 오버플로가 발생하는 경우. 32비트 int에서는 46341 × 46341 = 2147488281을 저장할 수 없어 음수로 돌아가므로 검사가 계속 통과하고 반복문은 √n을 훨씬 넘어 계속 실행됩니다. d에 64비트 타입을 사용하거나, 대신 d ≤ n / d를 비교하세요.
부동소수점 sqrt에서 상한을 구한 뒤 소수 부분을 버리는 경우. 여기서 double은 모든 n을 정확하게 표현하지만, 64비트 입력에서는 반올림으로 인해 실제 제곱근보다 1 작은 값이 나와 중요한 약수 하나를 건너뛸 수 있습니다. d * d ≤ n에는 이런 위험이 없습니다.

자주 묻는 질문3

숫자가 소수인지 확인하는 시간 복잡도는 얼마인가요?

√n까지의 시험 나눗셈은 O(√n) 시간과 O(1) 공간이 걸립니다. n이 2^31-1까지라면 최대 약 46,000번 나누면 되며, 짝수 제수를 건너뛰면 23,000번입니다. n-1까지 모든 제수를 시험하는 방법은 O(n)이며, 가장 큰 입력에서는 약 20억 단계가 걸립니다.

왜 n의 제곱근까지만 약수를 확인하나요?

약수는 곱이 n인 쌍 d와 n / d로 나타납니다. 두 수가 모두 √n보다 크다면 그 곱은 n보다 커집니다. 따라서 모든 쌍에는 √n 이하인 수가 하나 있고, 그때까지 약수가 나타나지 않으면 n은 소수입니다.

1은 소수인가요?

아니요. 소수는 정확히 두 개의 서로 다른 약수인 1과 자기 자신을 가지며, 1은 약수가 하나뿐입니다. 1을 제외하면 모든 양의 정수의 소인수분해가 유일하게 유지됩니다. 그래서 isPrime(1)은 false를 반환합니다.

def isPrime(n):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자

n = 29

예상 출력

true