백준 문제 중 1978번, 수학, ‘소수찾기’

백준 문제 중 1978번

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

문제

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

입력

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

출력

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

---

풀이

알고리즘애서 소수는 매우 중요한 역할을 한다. 그리고 소수를 구하는 방법중 가장 잘 알려진 에라스토의 체를 이용한다.

1. 자연수를 하나씩 스캔하며 소수 들로 나누어 진다면 소수가 아니고, 나누어 지지 않는다면 소수 이다.

2. 100의 약수 들은 1,2,4,10,25,50,100 이고 이중 (1,100) (2,50) (4,25) (10,10) 는 서로 곱하면 100이되고 두 쌍중 하나만으로도 나누어진다면 소수가 아님을 판단 할수 있고,이는 n의 제곱근 이하의 수들 까지만 소수들로 나누어 봐도 소수를 판단 할 수 있다.

위의 두가지를 코드로 구현 하면 아래와 같다.

from typing import List

 # x이하의 자연수 중 소수를 찾는 함수 정의
def find_prime(x:int)->List[int]:

     # x가 2일경우 조기종료
    if x==2:
      return [2]
    
     # 소수는 2를 제외하고 홀수 이므로 x//2
     # +1은 인덱스 범위가 벗어나는 오류 방지
    prime = [None]*(x//2+1)
    ptr = 0
     
     # 2는 소수 이므로 초기값에 추가 후 포인터 증가
    prime[ptr] = 2
    ptr+=1
     
     # 3도 소수 이므로 초기값에 추가 후 포인터 증가
    prime[ptr] = 3
    ptr+=1


    for n in range(5,x+1,2):
         
         # while문 종료후 i 초기화
        i=0
        
         # prime[i]^2 가 n보다 크면 종료
        while prime[i]*prime[i]<=n:
            
             # n이 소수로 나누어 지면 소수가 아님
            if n%prime[i]==0:
                break
            i+=1
          
         # n이 prime안의 어떤 소수로도 나누어 지지 않으면 n은 소수이다.
        else:
            prime[ptr] = n
            ptr+=1

     # 필요없는 None 제거
    prime = list(filter(lambda x: x!=None, prime))
    return prime

 # 1000이하의 소수리스트를 prime에 저장
prime = find_prime(1000)

 # 소수 판단 함수 선언
def is_prime(n:int)->bool:
    if n in prime:
        return True
    return False

cases = int(input())

nums = list(map(int,input().split()))

nums = nums[:cases]

answer = list(filter(is_prime, nums))

print(len(answer))

10
1 2 3 4 5 6 7 8 9
4

배운점

소수를 구하는 알고리즘은 알고 있었지만 코드로 구현 해본 적이 없었는데 코드를 구현할 줄 알게되었다.