[알고리즘/백준] 1978: 소수 찾기(python)

소수 판별하는 함수를 만들어서 풀었다.

약수의 존재 원리(?)를 이용해서 풀면 더 빠르게 해결 가능하다.

예를 들어서 설명하자면,

25의 약수는 1, 5, 25이다.

이는 다음과 같이 앞뒤로 짝을 지을 수가 있다.

1 x 25 = 25

5 x 5 = 25

25 x 1 = 25

1과 자기자신을 제외한 약수가 존재하는지 확인하려면, 자기자신의 제곱근(루트)까지만 확인하면 된다는 뜻이다.

어차피 약수들이 대칭적으로 짝을 이루기 때문에.

그러므로 25의 절반인 즉 루트25인 5까지만 나눠떨어지는지 확인하면 해당 숫자가 소수인지 아닌지를 알 수 있다.

from math import sqrt


def isprime(x):
    if x == 1:
        return False

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

    return True


N = int(input())
a = list(map(int, input().split()))
ans = 0
for i in a:
    if isprime(i):
        ans += 1

print(ans)