백준 1978번 파이썬 풀이: 소수 찾기

백준 1978번 소수 찾기

 

알고리즘 분류: 수학, 정수론, 소수 판정, 에라토스테네스의 체

 

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

 

1978번: 소수 찾기

문제

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

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

출력

주어진 수들 중 소수의 개수를 출력한다.

 

문제 파악

 

이 문제는 주어진 수들 중에서 소수의 개수를 찾는 문제이다.

 

소수의 정의는 1과 자기 자신을 제외한 자연수로 나눌 수 없는 자연수이다.

 

즉, 약수가 1과 자기 자신뿐인 1보다 큰 자연수라고 생각하면 된다.

 

때문에 1은 소수가 아니라는 점을 잘 체크해야한다.

 

 

코드

 

일단 입력값으로 주어지는 수들을 num_list라는 리스트에 담아둔다.

 

각각의 수들이 소수인지 판별하는 boolean값을 가지는 check라는 변수를 만들고

 

각각의 수의 check값이 True이면 소수이고 False이면 소수가 아닌것으로 해놓았다.

 

앞서 말했듯이 1은 소수가 아니기 때문에 num_list의 인덱스가 1이라면

 

check는 False가 되고 count는 올라가지 않는다.

 

소수는 약수가 1과 자기 자신밖에 없어야 하기 때문에 for문을 이중으로 돌리는데

 

range를 2이상 num_list[i] 미만으로 설정해준다.

 

만약 이 range 사이의 수로 나눴는데 나머지가 0이 된다면 check에 False를 넣어주고

 

break를 통해 반복문을 종료해준다.

 

이렇게 반복문을 진행하다보면 소수인 수가 있을때 마다 count가 1씩 증가하고

 

마지막으로 count를 출력해서 소수의 개수가 몇개있는지 출력해주면 된다.