[백준] 1978번 - 소수 찾기

문제

브론즈 2 - https://www.acmicpc.net/problem/1978

코드 구현

정답 코드

n = int(input())  # 수의 개수 N
nums = list(map(int, input().split()))  # 1000 이하의 자연수 N개

counts = []


def is_prime_num(x, counts):    # 소수인지 판별해야 하는 수 x
    prime_count = 0
    if(x <= 1):    # 1 이하면 소수 아님 (음수 포함)
        return 0
    for i in range(2, x):    # 2부터 x까지 나눠보기
        if (x % i == 0):     # 만약 2부터 x까지의 수인 i로 나눴을 때 나누어떨어지면 x는 소수가 아님
            return 0
        else:    # 나누어떨어지지 않으면 일단 오키 패스
            pass
	  # 다 돌고나서 모든게 나누어떨어지지 않아서 여기까지 살아남은 수면 소수다
    prime_count += 1
    counts.append(prime_count)
    return counts

for i in range(n):    # 입력받는 수의 개수 n만큼 돌려보기
    is_prime_num(nums[i], counts)

ans = 0
for i in counts:    # 최종 입력받은 수들 중 판별된 소수의 갯수 카운트
    ans += i
print(ans)

풀이

• 소수 판별 함수를 만들어서 입력받는 개수 n만큼 돌려보는 형식으로 구현
• 소수는 1과 자기 자신만을 약수로 갖는 수다.
• 소수 판별 함수는 다음과 같은 기준으로 소수인지 아닌지 판별한다.
  • 1 이하면 소수가 아니다.
  • 2부터 자기 자신에 해당하는 수 전까지 모두 나눠봤을 때 한번이라도 나누어떨어지게 된다면 소수가 아니다. (약수가 존재한다는 뜻)