[백준] 1978 소수 찾기 (Python 파이썬)

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

1978번: 소수 찾기

문제 설명

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

---

풀이 과정

소수란, 1과 자기자신을 제외한 나머지 수로 나누어 떨어지지 않는 수이다.

그래서 소수를 판별하는 가장 간단한 방법은

2부터 자기자신 - 1 까지 for문을 돌면서 나누어 떨어지는지 확인하는 것이다.

 

하지만, 모두 확인할 필요 없이 제곱근까지만 확인을 하면 된다.

 

그 이유는 약수들의 곱이 서로 대칭을 이루기 때문인데

예를 들어, 16이라는 수가 있을 때

16의 약수는 1, 2, 4, 8, 16이며

약수들의 곱으로 나타내면 (1, 16) (2, 8) (4, 4) (8, 2) (16, 1) 다섯쌍의 곱으로 나타낼 수 있다.

 

이렇게 제곱근 4x4를 기준으로 양 옆으로 대칭을 이루기 때문에 제곱근 까지만 검사를 하면 된다.

 

이를 파이썬으로 나타낸 코드는 다음과 같다.

import math

n = int(input())
numList = list(map(int, input().split()))

def isPrime(x):
    if x == 1:
        return False
    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            return False
    return True

cnt = 0
for num in numList:
    if isPrime(num):
        cnt += 1

print(cnt)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !