[수학] 백준 1978 소수 찾기 with python

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

import math

def is_prime_num(num):
    if num == 1:
        return 0
    for i in range(2, int(math.sqrt(num))+1):
        if num % i == 0:
            return 0
    return 1


n = int(input())
lst = list(map(int, input().split()))
cnt = 0
for num in lst:
    if is_prime_num(num) == 1 :
        cnt += 1
print(cnt)

각 수가 소수인지 아닌지 판별하는 문제였다.
소수는 1과 자기자신만을 약수로 갖는 수, 곧 다른 숫자로 나누어 떨어지면 안된다는 뜻이다.
36의 약수를 예시로 들어보자
1 2 3 4 6 9 12 18 36
6을 기준으로 왼쪽과 오른쪽이 짝을 이루는 것을 확인할 수 있다.
따라서 2부터 36의 제곱근인 6까지만 나눠보고 뒤는 굳이 안 나눠봐도 된다!
제곱근을 얻어주는 math.sqrt()를 사용하면 float형이기 때문에 int로 바꿔준다.
굳!