[python]- 에라토스테네스의 체 (소수 찾기)

에라토스테네스의 체

 

 

에라토스테네스의 체를 통해 소수를 찾을 수 있다.

중첩 For문을 사용하지 않아도 되어서 더 빠르다.

 

예를 들어 1부터 100까지의 숫자중 소수를 찾는다면 

먼저 1을 제외한다.

 

그런 후 2를 제외한 2의 배수들을 제거한다. 2는 짝수 중의 유일한 소수이기 때문이다.

 

3과 5 7도 이와 같은 방식으로 지운다. 

 

이것들을 아래코드로 표현하자면,

이 문제의 범위가 1,000,000이라 MAX값을 이것으로 놔둔다.prime이라는 새로운 배열을 만들어 MAX번째 인덱스까지 값을 True로 만든다.prime의 1번인덱스는 소수가 아니라 False로 미리 변환해준다.

 

for문의 범위를 2부터 MAX의 제곱근을 정수형으로 변환한데까지 해준다.그런 후 만약 prime[i]값이 True라면 j를 2로 두고 ,i*j가 MAX보다 같거나 작은 동안 while문을 반복해준다.이때 i*j의 값들은 반드시 소수가 아니기 때문에 이 값들의 인덱스의 값을 False로 변환한다.그런 후 j를 1씩 늘려간다. for문이 끝나면 prime 배열의 값들은 배수인 값들은 False가 된다. True인 값들만 출력하게 되면 범위 내의 소수의 값들을 구할 수 있다.

 

아래코드는 소수의 개수라서 아래 for문을 추가해주었다.