[Python/파이썬] 백준 1978번: 소수 찾기

문제 설명

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

 

 

 

 

 

 

제출한 코드

import math

num = int(input())
lst = list(map(int, input().split()))
answer = 0

def prime(n):
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True

for i in range(num):
    if lst[i] != 0 and lst[i] != 1 :      
        if prime(lst[i]) == True:
            answer += 1
print(answer)

 

 

 

 

결과

 

 

 

후기

1부터 n까지 일일히 검사하는 방법도 있지만, 이론적으로 n의 제곱근까지만 검사하면 된다. 하지만 이도 시간이 꽤 소요되는 방법이다.

시간을 절약하는 다른 방법으로는 에라토스테네스의 체가 있는데, 이는 다음에 써보도록 하겠다.