[백준/Python] 1978번 : 소수 찾기

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

1978번: 소수 찾기

 

- 풀이

import sys
input = sys.stdin.readline

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

for i in num_list :
    if i == 1 :
        n -= 1
        continue
    for j in range(2, int(i**0.5)+1) :
        if i%j == 0 :
            n -= 1
            break

print(n)

1. n = int(input))을 통해 전체 갯수를 입력받았음. 추후 소수가 아닌 경우에는 여기서 제외하는 방식으로 진행함

2. num_list를 for문을 통해 차례대로 값을 확인하며 만약 1인 경우에는 소수가 아니므로 n에서 1을 빼줌

3. 그 후에는 2부터 int(i**0.5) 까지의 값을 돌아가면서 나누었을 때 떨어지는 값이 있으면 n에서 1을 빼줌 : 나누어진다는 의미는 소수가 아니라는 의미이므로

- int(i**0.5)는 주어진 값의 제곱근을 의미하는데 값이 나눠질때는 pair로 존재하는데 pair의 앞 값이 최대인 경우가 제곱근일 때로 약수의 경우에는 제곱근까지만 값을 확인하면 효율적으로 식을 만들 수 있음.

예를 들어서 36의 경우에는 (2, 18) (3, 12) (4, 9) (6, 6) 으로 2부터 6까지만 돌면 해당 값의 모든 약수를 알 수 있음!