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

www.acmicpc.net/problem/1978  

1978번: 소수 찾기

 

 

소수: 약수가 1과 자기 자신밖에 없는 수

 

소수를 구하는 법에는 크게 두 가지가 있다.

1. 소수의 정의 이용

- N이 소수인지 알아보기 위하여 2 부터 N-1까지 나머지 연산을 해본다.

- 시간복잡도 $O(n)$

 

2. 약수의 특징 이용

- N의 가장 작은 약수는 2이다. 약수는 $\sqrt{N}$을 기준으로 대칭이다. 2의 대칭인 수는 $2/N$이다. $2/N+1$부터 N-1까지 약수가 없어야 소수 이므로 2부터 $N/2$까지 나누어 떨어지는지 검사한다.

- 시간복잡도 $O(n)$

 

- 또 다른 방법으로 2부터 $\sqrt{N}$까지 구하는 방법이 있다. 

- 자연수 N이 있을 때, N의 약수는 $\sqrt{N}$을 기준으로 대칭을 이룬다.

- 그러므로 1을 제외하고 2부터 $\sqrt{N}$ 까지 나누어떨어지는지에 대해서만 검사를 하면 된다.

- 즉, N이 소수가 되려면, 2보다 크거나 같고, $\sqrt{N}$보다 작거나 같은 자연수로 나누어 떨어지면 안된다.

- 시간복잡도 $O(\sqrt{N})$

 

def is_prime(n):
    # 소수면 True
    if n<2:
        return False
    i=2
    while i*i <= n:
        if n%i == 0:
            return False
        i += 1
    return True

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

cnt=0
    
for a in arr:
    if is_prime(a): cnt += 1

print(cnt)