소수 판별하는 함수를 만들어서 풀었다.
약수의 존재 원리(?)를 이용해서 풀면 더 빠르게 해결 가능하다.
예를 들어서 설명하자면,
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)
smilegate