백준 1978번 풀이

문제

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

1978번: 소수 찾기

N개의 수가 주어질 때, 여기서 소수의 개수는?

 

소수?

1과 자기 자신만 약수로 가지는 수이다. 참고로 1은 소수가 아님.

 

풀이

import sys
N = int(sys.stdin.readline())
b = list(map(int,sys.stdin.readline().split()))
prime = []
def isprime(a):
    if a < 2:
        return False
    for i in range(2,a):
        if a % i == 0:
            return False
    else:
        return True
for j in b:
    if isprime(j):
        prime.append(j)
print(len(prime))

참고로 함수 쓰지 말라고는 안 했다.

def isprime(a):
    if a < 2:
        return False
    for i in range(2,a):
        if a % i == 0:
            return False
    else:
        return True

이 함수는 에라토스테네스의 체에서 썼던건데, 2보다 작거나(1은 소수가 아님) 자기 자신 외에 다른 수로 나눠떨어지는 수는 전부 false 처리하고 나머지를 true처리한다.