소수 판별 알고리즘 단계별 설명

개념 정리

1. number % 3 == 0은 숫자가 3으로 나누어 떨어진다는 의미입니다. 이것은 그 숫자가 홀수인지 여부와는 관련이 없습니다.

   • 홀수인지 확인하려면 number % 2 != 0 또는 number % 2 == 1을 사용합니다.

2. 숫자가 3으로 나누어 떨어진다면 (예: 3, 6, 9, 12...), 그 숫자는 소수가 아닙니다(3 자체는 예외).

3. 소수 판별을 위해서는 2부터 해당 숫자의 제곱근까지의 모든 수로 나누어 봐야 합니다.

소수 판별 알고리즘 단계별 설명

1. 1은 소수가 아닙니다.
2. 2는 소수입니다.
3. 3 이상의 수에 대해:
   • 2부터 number의 제곱근까지 반복하면서
   • 각 수로 number를 나누어 봅니다.
   • 만약 나누어 떨어지는 수가 있다면(나머지가 0), 그 수는 소수가 아닙니다.
   • 모든 수로 나누어 떨어지지 않으면 소수입니다.

코드 구현 힌트

func primeNumber(_ number: Int) {
    // 1은 소수가 아님
    if number <= 1 {
        print("소수가 아닙니다")
        return
    }
    
    // 2부터 제곱근까지 나누어 떨어지는지 확인
    let sqrtNum = Int(Double(number).squareRoot())
    
    for i in 2...sqrtNum {
        if number % i == 0 {
            // 나누어 떨어지면 소수가 아님
            print("소수가 아닙니다")
            return
        }
    }
    
    // 여기까지 왔다면 소수임
    print("소수입니다")
}

제곱근까지만 확인하는 이유

소수는 1과 자기 자신으로만 나누어 떨어지는 수입니다. 어떤 수 N이 소수인지 판별하기 위해서는 2부터 N-1까지의 모든 수로 나누어 봐야 할 것 같지만, 실제로는 제곱근까지만 확인해도 충분합니다.

그 이유는 다음과 같습니다:

1. 만약 N이 합성수(소수가 아닌 수)라면, N = a × b 형태로 표현할 수 있습니다(a와 b는 1과 N이 아닌 정수).

2. 이때 a와 b 모두 N보다 작습니다. 그런데 만약 a와 b 모두 √N보다 크다면:

   • a > √N 이고 b > √N 이면
   • a × b > √N × √N = N 이 됩니다.
   • 이는 a × b = N이라는 가정에 모순됩니다.

3. 따라서 a와 b 중 적어도 하나는 반드시 √N 이하여야 합니다.

4. 이 말은 N이 합성수라면, 반드시 2부터 √N 사이에 N의 약수가 존재한다는 의미입니다.

5. 그러므로 2부터 √N까지만 확인해도 소수 여부를 판별할 수 있습니다.

예시

예를 들어, 36이 소수인지 판별하려면:

• √36 = 6
• 2부터 6까지만 확인하면 됩니다.
• 36은 2로 나누어 떨어지므로 소수가 아닙니다.

만약 37이 소수인지 판별하려면:

• √37 ≈ 6.08
• 2부터 6까지 확인합니다.
• 37은 2, 3, 4, 5, 6 중 어느 것으로도 나누어 떨어지지 않으므로 소수입니다.

이렇게 제곱근까지만 확인하는 것은 알고리즘의 효율성을 크게 향상시킵니다. N까지 모두 확인하는 것보다 훨씬 빠르게 소수 여부를 판별할 수 있습니다.

좋은 질문입니다. "만약 a와 b 모두 √N보다 크다면"이라는 가정을 세운 이유를 설명해 드리겠습니다.

이 가정을 세운 이유

이 가정은 귀류법(proof by contradiction) 을 사용하기 위한 것입니다. 귀류법은 어떤 명제가 참임을 증명하기 위해, 그 명제의 반대가 성립한다고 가정했을 때 모순이 발생함을 보여주는 증명 방법입니다.

여기서 증명하려는 명제는:

"N이 합성수일 때, N의 약수 중 적어도 하나는 √N 이하이다."

이 명제를 증명하기 위해 반대 상황을 가정합니다:

"N의 모든 약수가 √N보다 크다."

그런데 N이 합성수라면 N = a × b 형태로 표현할 수 있습니다(여기서 a와 b는 1과 N이 아닌 N의 약수).

만약 a와 b 모두 √N보다 크다면:

• a > √N 이고 b > √N 이므로
• a × b > √N × √N = N 이 됩니다.

하지만 이는 a × b = N이라는 원래 조건에 모순됩니다. 따라서 원래 가정(모든 약수가 √N보다 크다)이 틀렸다는 것을 증명한 것입니다.

결론

이 모순을 통해 우리는 N이 합성수일 때 N의 약수 중 적어도 하나는 반드시 √N 이하라는 것을 알 수 있습니다. 이것이 소수 판별 알고리즘에서 제곱근까지만 확인해도 되는 수학적 근거입니다.

이 가정은 증명 과정에서 모순을 이끌어내기 위한 논리적 도구로 사용되었습니다. 결국 이 가정이 틀렸다는 것을 보여줌으로써, 우리가 원하는 명제(약수 중 하나는 √N 이하)가 참임을 증명한 것입니다.