[ 알고리즘/ Python ] 소수 구하기 : 에라토스테네스의 체

코테, 백준 문제를 풀다보면 '소수'를 구하는 문제가 꽤나 나온다. 

소수를 사람의 손으로 풀기에는 다소 어려움이 있을 수 있다. 2,3,5,7 .. 정도는 괜찮지만 컴퓨터 암호화에 사용되는 아주 큰 소수는 판별하기 어렵다. 그럼 컴퓨터에게 이 소수를 구하라고 시키는 프로그램을 작성해보자 ~ 

1. 소수 

1과 그 수 이외의 자연수로는 나눌 수 없는 자연수

소수는 2,3,5,7...에서 볼 수 있듯 약수가 2개라는 특징을 가진다. 이러한 특징 때문에 1은 소수가 될 수 없다. 

import math
n = int(input())

def isPrime(n):
    if n <=1 :
        return False
    for i in range(2, int(math.sqrt(n))+1):
        if (n%i == 0) :
            return False
    return True

완전 제곱수를 제외한 약수는 √N 을 기준으로 쌍을 이룬다. 

따라서 1~√N 까지 N의 약수를 확인해주면 소수를 조금 더 빠르게 구할 수 있다 ! 

(2부터 √N 까지 약수가 하나도 없으면 따로 연산해주지 않아도 √N ~N-1까지도 약수가 없다 ! )

 

 

2. 에라토스테네스의 체 알고리즘 

- 다수의 자연수에서 소수 여부를 판별할 때 사용하는 대표적인 알고리즘 

- N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다.

 

n = int(input())
a = [False,False] + [True]*(n+1) # 0,1을 제외하고 2부터 모든 수가 소수(True)인 것으로 초기화
primeList = [] # 소수를 넣어줄 리스트

for i in range(2,n+1):
    if a[i] : # a[i] == True, 즉 a[i]가 소수라면
        primeList.append(i)
        for j in range(2*i,n+1,i): # 2i부터 i의 배수들 False로 지우기
           a[j] = False

print(primeList)

1000000이하의 소수를 출력한다. 

 

 3. 구체적인 동작과정 

1. 1을 제외하고 모든 수가 소수(True)라고 가정
   
   
2. 남은 수 i 중에서 처리하지 않은 가장 작은 수를 찾아 아래 과정을 반복한다.
   
   2-1) 탐색하고 있는 수(i)가 소수라면 i의 배수 지우기 → False 입력
   2-2) 탐색하고 있는 수(i)가 소수가 아니라면 스킵 →False상태 유지 

 

 

 

4. 관련 문제 

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

6219번: 소수의 자격

 

1929번: 소수 구하기

 

 

[참고 및 출처]

 

https://wikidocs.net/21638

https://freedeveloper.tistory.com/392

한국항공대학교 KOALA 알고리즘 학회 '브론즈에서 플래티넘' 강의자료