백준 - 1978번 / 소수

소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수이다.

* 1은 소수가 아니다

 

어떤 수가 소수인지 확인하기 위해서는 n보다 작은 수로 나누어지는지 확인해보면 된다.

2부터 n까지 모두 확인해도 되지만 사실 √ n 까지만 확인하면 된다. 왜냐하면 수가 수를 나누기 위해서는 그 몫이 항상 필요하며, 나누는 수와 몫 중 하나는 반드시 √ n 이하이기 때문이다.

 √ 108 = 약 10.33이다.

만약 2 ~ √ n 까지 나눠보았는데 나눠지지 않는다면 소수라고 할 수 있다.

 

1978번 - 소수 찾기

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

1978번: 소수 찾기

T = int(input())
cnt = T
num = map(int, input().split())
for n in num:
    if n == 1: cnt -= 1
    i = 2
    while i * i <= n:
        if n % i == 0:
            cnt -= 1
            break
        else:
            i += 1
print(cnt)

i의 제곱이 n이 작을 때까지만 확인하면 소수인지 확인할 수 있다.

 

 

 

참고한 사이트

https://ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98_(%EC%88%98%EB%A1%A0) 

소수 (수론) - 위키백과, 우리 모두의 백과사전