[1] 소수찾기 - 에라토스테네스의 체

소수의 정의

소수라 함은 자신보다 작은 두개의 자연수를 곱하여 만들수 없는 1보다 큰 자연수 이다.

 

예를 들어 2, 3, 5, 7 ,11 ... 등이 있다.

 

 

 

---

 

 

소수 구하기 

소수를 구하는 대표적인 방법은 고대 그리스 수학자 에라토스테네스가 발견한 <에라토스테네스의 체> 방법을 사용하는 것이다.

 

이 방법은 2부터 n까지의 자연수 수열에서 가장 앞에 있는 숫자가 소수가 되고 그 뒤로 그수의 배수들을 전부 지운다.

 

그리고 그 다음 남아있는 숫자가 소수가 되고 또 그 뒤로 그 수의 배수들을 전부 지운다

 

...

 

이 과정을 반복하다보면 n까지의 소수들을 찾을 수 있다.

 

아래 자료를 보면 쉽게 이해가 될것이다.

 

 

출처 : 위키백과

 

 

이를 코드로 구현하는 것은 어렵지 않다.

 

아래는 파이썬으로 구현한 코드이다.

n = int(input(""))

arr = list(range(2,n+1))
answer = []
while(len(arr) != 0):
    tmp = arr[0]
    answer.append(tmp)
    arr.remove(tmp)
    for i in arr:
        if(i%tmp == 0):
            arr.remove(i)

print(answer)