소수 알고리즘

최근에 간단한 알고리즘을 풀다가 소수를 찾는 알고리즘에 대해 생각해봤는데, 이중 for문을 통해서 구현하는 방법밖에 생각이 안났다. 이건 아니다 싶어 구글링을 하다가 정말 멋있는 게시물을 발견하여 아래에 첨부한다

 

https://st-lab.tistory.com/81

JAVA [자바] - 소수 구하는 알고리즘 및 구현

 

위의 블로그에서는 소수를 찾는 알고리즘을 3가지를 제시한다.

 

1. 2부터 차례대로 나눠보는 방법

 

2. 제곱근을 이용하여 for문의 탐색길이를 줄이는 방법

 

3. 에라토스테네스의 체를 이용하여 위의 두 방법보다 더욱 개선된 방법

 

 

에라토스테네스의 체는 들어보기는 했지만 실제로 제대로 찾아본 것은 처음이라 너무 신기했다. 자세한 설명은 위의 게시글에 있으니 생략하고 에라토스테네스의 체를 이용하는 방법을 하단에 기술하겠다.

 

 

1. n+1 크기의 boolean type 배열을 만든다.

2. 0, 1은 소수가 아니므로 true로 지정한다. (소수:false, 소수가 아닌 수:true)

3. 숫자 2 ~ n의 제곱근까지 반복문을 진행한다.

  3-1. 배열의 값이 true이면 continue를 실행한다.

  3-2. 배열의 값이 false라면 i*i ~ n까지 i를 계속 더해가며 그 값들을 모두 true로 정해준다.

        예) i = 3 이라면, 배열[9] = true, 배열[12] = true ... 등

* 만약 n이 2보다 작다면 0만 리턴하면 된다. (2보다 작은 소수는 없으므로)

 

 

이제 소수 알고리즘 문제를 풀어봐야겠다! 잘 풀 수 있을 것 같은 기분이 든다!