[Python] 백준 1978번: 소수 찾기(파이썬,수학,정수론)

문제 출처:

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

1978번: 소수 찾기

문제

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

 

입력

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

 

출력

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

풀이 방법

백준 17425 약수의 합(https://yoon-e.tistory.com/7) 문제와 매우 유사하다. 

	1	2	3	4	5	6	7	8
1	1	1	1	1	1	1	1	1
2		2		2		2		2
3			3			3
4				4				4
5					5
6						6
7							7
8								8
sum	1	3	4	7	6	12	8	15

'소수'의 정의에 대해 생각해보면, 2 이상의 자연수 중 1과 자기자신만을 약수로 가지는 자연수를 말한다. 즉, 약수의 합이 1+N 이라면 그 N은 약수인것을 알 수 있다.

 

이 문제에선 N은 최대 1000까지 주어지므로, 1000까지의 f(N)을 구해둔다면, 입력 데이터들을 for loop 한번으로 소수의 개수를 구할 수 있다.

import sys
x = int(sys.stdin.readline())
data = list(input().split())

savechartTemp = [1]*1001



for i in range(2,1001):
    for j in range(1,(1000//i)+1):
        savechartTemp[j*i] = savechartTemp[j*i] + i


sol = 0

for i in data:
	#약수의 합(savechartTemp[int(i)])가 i+1과 같다면 i는 소수이다.
    if savechartTemp[int(i)] == int(i)+1 and int(i)!=1:
        sol = sol+1


print(sol)