백준 1978번 : 소수 찾기 (Python)

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

n = int(input())
nums = list(map(int, input().split()))
prime = 0

for i in nums :
    prime_j = 1    # 특정 숫자가 소수인지 표시하는 변수
    root_i = int(i**(1/2)) + 1
    for j in range(2, root_i) :    # 2부터 제곱근까지 차례로 나눠서
        if i % j == 0 :    # 소수가 아니면 prime_j = 0을 넣어서 소수가 아님을 체크
            prime_j = 0
            break
    prime += prime_j    # 소수임이 확인되면 prime 값에 1을 더해줌
print(prime - nums.count(1))    # 1은 소수로 계산되므로 1의 개수만큼 빼줌

여러 방법이 있겠지만, 앞에서부터 숫자 하나씩 소수인지 아닌지 검증해서 세는 방법을 사용했다.

특정 자연수 N이 소수인지 확인하려면 물론 N보다 작은 모든 자연수로 나눠봐도 되지만,

루트N 보다 작은 자연수로만 나눠줘도 충분하다.

따라서 입력받은 숫자들 각각에 대해 그 과정을 반복해 소수인지 아닌지 확인했다.

마지막으로 이 방법을 사용하면 1도 소수로 계산되므로 마지막에 1의 개수만큼 빼준다.