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

• 문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

조건
1. 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.
2. 주어진 수들 중 소수의 개수를 출력한다.

 

• 코드

# 입력부
n=int(input());
prime=list(map(int,input().split()));

# 처리부
def isprime(k):
    if(k==1):
        return 0;
    for i in range(2,k,1):
        if(k%i==0):
            return 0;
    return 1;

count=0;

for i in range(len(prime)):
    if(isprime(prime[i])==1):
        count+=1;

# 출력부
print(count);

 

• 문제 풀이

이번엔 사용자 정의 함수를 써서 문제를 풀었다.

소수인지 아닌지 판별해서, 소수이면 1을 반환, 아니면 0을 반환하는 함수이다.

 

소수 판별 방식은 판별하고자 하는 수를 2부터 판별하고자 하는 수까지 나눈다.

이 때, 나눠 떨어지는 수가 있다면 소수가 아니다. 나눠 떨어지는 수가 없다면 소수다.

이를 에라토스테네스의 체라고도 부른다. (수가 간단하면 상관없는데, 수가 커질수록 복잡도 역시도 커진다)

 

• 여담

학기 중 교수님께서 소수 판별 문제 시험에 낸다고 하셔서 열심히 코드 외워 갔는데, 결국 시험에 나오지 않았다...ㅠ

 

---

 

코드가 이상하거나, 이해가 되지 않는 부분은 댓글 남겨주시면 답변드리겠습니다! :)