[python 기초] 백준: 1978번 / 함수형 문제풀기

📍 In a nutshell...

• 소수 판단 여부를 함수로 만들어보자
  • True, False 둘 중 하나를 반환값으로 지정
  • return과 동시에 함수는 종료 처리된다
  • 좀 더 객체지향적인 코드가 가능하다 (캡슐화, 은닉)

문제)
주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.
첫 줄에 수의 개수 N이 주어진다. N은 100이하이다.
다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

풀이)

우선, 소수란 1과 자기 자신 외에 나눠지지 않는 수를 말한다.
기본적으로 위의 문제를 풀어보면 아래와 같다.

N = int(input())
X = list(map(int, input().split()))

result = []

for x in list(X):
    if x == 1: 
        pass
    else:
        for i in range(2,x):
            if x%i == 0:
                break
        else:
            result.append(x)

print(len(result))

• 1은 소수가 아니므로, 제외시킨다
• 2부터 소수에 대한 판단을 시작한다
  • 2 이상의 수라면, 2부터 차례 대로 나눠본다
  • 만약 어떤 수로 나눴을 때 0이 된다면 break (소수가 아님)
  • 자기 자신-1 까지 나눠지지 않으면, 즉 소수라면 result에 더한다
• result의 개수를 구한다

N = int(input())
X = list(map(int, input().split()))

#소수를 판단하는 함수 is_prime
def is_prime(n):
    if n == 1:
        return False

    for i in range(2,int(n**(1/2))+1):
        if n%i == 0:
            return False

    return True

cnt = 0
for x in X:
	if is_prime(x): cnt += 1

print(cnt)

• 소수를 판단하는 함수 is_prime의 로직은 아래와 같다
  • 1이면 False 다
  • 2 이상의 수라면, 2부터 차례 대로 나눈다
    • 어떤 수에 의해 나눠진다면 False (소수가 아님)
    • int(n**(1/2)) 까지 나눠지지 않는다면 True
• is_prime(x) 이 True라면 카운트한다

나누기 범위를 자기자신-1이 아니라 int(n**(1/2))로 하는 이유는 아래와 같다.

• n**(1/2)은 루트와 동일하다 (1/2 제곱근)
• 16을 예로 들어보자
  • 16의 1/2 제곱근은 4다.
  • 2에서 나눠진다면, 8로도 나눠짐이 성립된다
• 즉, 데칼코마니 같은 관계로, 나머지 절반까지 가지 않아도 소수 여부를 판단할 수 있으며 시간 복잡도도 줄일 수 있다.

출처: 백준