백준 - 1978 소수 찾기 [정수론]

 

1978번: 소수 찾기

 

해당 문제는 주어진 숫자가 소수인지 판별하는 문제입니다.

낮은 난이도이기에 어떠한 방식으로 풀어도 통과가 됩니다.

대표적인 3가지 방법으로 풀어보겠습니다.

 

1. 일반적인 방법

가장 일반적인 방법으론 2부터 1씩 늘려가며 해당 숫자가 나누어 떨어지는지 보는 방법입니다.

// Java
static boolean isPrime(int number) {
    if (number <= 1) {
        return false;
    }
    for (int i = 2; i < number; i++) {
        if (number % i == 0) {
            return false;
        }
    }
    return true;
}

 

2. 제곱근을 이용한 최적화

예를 들어 20이라는 수의 약수를 보겠습니다.

• 1 X 20 = 20
• 2 X 10 = 20
• 4 X 5 = 20
• 5 X 4 = 20
• 10 X 2 = 20
• 20 X 1 = 20

가운데 약수를 기준으로 등식이 모두 대칭입니다.

이점을 이용하여 가운데 약수(제곱근)까지만 나누어 떨어지는지 확인하면 됩니다.

// Java
static boolean isPrime(int number) {
    if (number == 2) {
        return true;
    }
    if (number < 2 || number % 2 == 0) {
        return false;
    }
    for (int i = 3; i * i <= number; i += 2) {
        if (number % i == 0) {
            return false;
        }
    }
    return true;
}

추가적으로 2를 제외한 모든 짝수는 2로 나누어 떨어지므로 소수가 아닙니다.

해당 부분을 추가한 조건문을 추가해주었고, for문에서는 홀수만 검사하도록 개선했습니다.

 

3. 에라토스테네스의 체

해당 알고리즘은 여러 개의 수가 소수인지 판별할 때 사용하는 방법입니다.

해당 알고리즘을 이용하면 N이하의 모든 소수를 찾을 수 있습니다.

1. 2부터 N까지의 모든 자연수를 나열한다.
2. 나열된 숫자중 아직 처리하지 않은 가장 작은 수 i를 찾는다.
3. i를 제외하고 i의 배수를 모두 제거한다.
4. 2번과 3번 과정을 반복할 수 없을 때까지 반복한다.

# Python
n = int(input())
nums = list(map(int, input().split()))
arr = [False, False] + [True] * (max(nums) - 1) # 사용성을 위해 0, 1을 추가해줌
answer = 0

# 에라토스테네스의 체에 소수를 제외한 나머지 숫자를 False로 변경해줌
for i in range(2, len(arr)):
    if arr[i]:
        for j in range(i + i, len(arr), i):
            arr[j] = False

# 소수 여부 검사
for num in nums:
    if arr[num]:
        answer += 1

print(answer)

다만, 단점으로는 메모리가 많이 필요하다는 단점이 있습니다. (N만큼의 크기만큼의 배열을 생성해야 하므로)

 

깃허브 전체 코드

https://github.com/Ksiyeong/Algorithm/tree/main/%EB%B0%B1%EC%A4%80/Bronze/1978.%E2%80%85%EC%86%8C%EC%88%98%E2%80%85%EC%B0%BE%EA%B8%B0