[Python]수학2 백준 1978

문제

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

일반적으로 소수인지를 알기위해선 n보다 작은수 모든수로 나눠서 확인해야한다.

위에 방법에서 조금 발전시킨다면 n/2보다 작은수까지만 나눠봐도 알 수 있다. 최소가 2일

테니깐1은 소수가 아니다. 소수는 1이 아닌 자연수 중에서 1과 자기 자신 이외의 약수를 갖

지 않는 수입니다. 

이제 소수를 구하고자하는 범위가 정해져있을때 소수를 구하는 방법을 알아보자.

에라토스테네스의 체를 이용하는 방법이다.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

위 알고리즘 대로 한번 코드를 작성해보자

import sys
 
 
n=int(input())
prime_number=[2 for _ in range(1001)]
for i in range(1,1001):
   if i==1:  #1은 소수가아님
        prime_number[i]=0
   elif prime_number[i]!=0:  #이전에 0으로 표시도있다면 건너뛴다.
        prime_number[i]=1   #소수로 표시
        mul=2               
        j=i
        while(j*mul<=1000):     #소수의 배수는 모두 소수가 아니다.
            prime_number[j*mul] = 0
            mul+=1
 
 
n_list=list(map(int,sys.stdin.readline().split()))  #입력숫자 리스트로 저장
result=0
for i in n_list:         
    if prime_number[i]==1: #소수로 표시되어있으면 1증가
        result+=1
 
print(result)