백준 - 1978번 소수 찾기 python 문제풀이 [Hellfer]

https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

🔷 알고리즘 분류 - 수학, 정수론, 소수 판정 

난이도 - 브론즈 2

is_prime 함수는 주어진 숫자가 소수(prime number)인지 아닌지를 판별하는 함수입니다.

소수는 1과 자기 자신 외에 어떤 수로도 나누어 떨어지지 않는 1보다 큰 양의 정수를 말합니다. 

즉, 소수는 약수가 1과 자기 자신 두 개뿐인 수를 의미합니다.

is_prime 함수는 다음과 같은 과정으로 작동합니다:

1. 입력받은 숫자 num이 1인 경우, 1은 소수가 아니므로 False를 반환합니다.

2. num이 1이 아니라면, 2부터 num의 제곱근까지의 모든 수로 num을 나누어 봅니다.

만약 num을 나누는 수가 있다면, num은 소수가 아니므로 False를 반환합니다.

3. 2부터 num의 제곱근까지의 모든 수로 나누어 봤는데도 나누어 떨어지는 수가 없다면, num은 소수이므로 True를 반환합니다.

제곱근까지만 확인하는 이유는, 어떤 수 num이 소수가 아니라면 그 약수는 반드시 sqrt(num) 이하에 존재하기 때문입니다.

 

 따라서 모든 수를 확인할 필요 없이 제곱근까지만 확인하면 소수를 효율적으로 판별할 수 있습니다.

🔶 문제 풀이 - (is_prime) 함수를 이용한 풀이

# 소수를 판별하는 함수를 정의합니다.
def is_prime(num):
    if num == 1:  # 1은 소수가 아니므로 False를 반환합니다.
        return False
    else:
        # 2부터 num의 제곱근까지의 수로 num을 나누어 봅니다.
        for i in range(2, int(num**0.5) + 1): 
            # 만약 num이 i로 나누어 떨어진다면, num은 소수가 아니므로 False를 반환합니다.
            if num % i == 0: 
                return False
        # 위의 반복문에서 num이 어떤 수로도 나누어 떨어지지 않았다면, num은 소수이므로 True를 반환합니다.
        return True

# 사용자로부터 정수 N을 입력받습니다.
N = int(input())
# 사용자로부터 N개의 수를 입력받아 정수로 변환하고 리스트로 만듭니다.
numbers = list(map(int, input().split()))
# 소수의 개수를 저장할 변수 count를 0으로 초기화합니다.
count = 0

# 리스트 numbers에 있는 각 숫자에 대해
for num in numbers:
    # 그 숫자가 소수라면
    if is_prime(num):
        # count를 1 증가시킵니다.
        count += 1

# 소수의 개수를 출력합니다.
print(count)

🔶 코드풀이

for i in range(2, int(num**0.5) + 1): 

 

해당 코드는 입력된 숫자 num의 제곱근까지의 수 중에서 num이 나누어 떨어지는지 확인하는 코드입니다.

예를 들어 num이 36이라고 가정해 봅시다. 

 

이때 num**0.5는 6이므로, range(2, int(num**0.5) + 1)은 range(2, 7)이 됩니다.

 

따라서 i는 2, 3, 4, 5, 6을 차례대로 가집니다.

 

num = 36
for i in range(2, int(num**0.5) + 1):
    print(i)

 

위 코드를 실행하면 다음과 같은 출력 결과가 나옵니다.

 

2
3
4
5
6

 

이렇게 2부터 num의 제곱근까지의 숫자를 i로 하여 반복문을 수행하는 이유는, num이 소수가 아니라면 그 약수는 반드시 num의 제곱근 이하에 존재하기 때문입니다. 

 

따라서 num의 제곱근까지만 검사하면 num이 소수인지 아닌지를 빠르게 판별할 수 있습니다.

 

🤗파이팅입니다~ 여러분!!🤗