코드 자체는 별거 없다. for문이 두개가 돌면서 i는 소수인지 아닌지 확인하려는 숫자, j는 그걸 확인하기 위한 값이다.
소수라 함은 자기자신으로만 나누어 떨어지는 수를 말하며 그렇기 때문에 소수인지 아닌지 확인하는 j값이 i값과 같은 크기일때까지만 커지면 된다.
또한 자기자신외에 다른 숫자로 나누었을시 나누어 떨어지면 이 숫자는 소수가 아니기 때문에 더이상 j값을 증가시킬 필요가 없다.
그런데 여기서, 숫자는 제곱근을 기준으로 대칭형의 곱셈형식으로 나타낼 수 있다.
예를 들어 12의 경우 1*12, 2*6, 3*4, 4*3, 6*2, 12*1 같이 대칭형을 이룸을 알 수 있다.
그렇기 때문에 원하는 숫자의 제곱근까지 확인하면, 그 이상은 확인하지 않아도 알 수 있기 때문에 제곱근함수(sqrt)를 사용하여 더욱 단축할 수 있다.
소스에서는 제곱근부터 시작하여 소수인지 확인하려는 숫자 i와 그걸 확인하기 위한 숫자 j가 같을때 출력하도록 짜보았다.
시간 복잡도 상으로는 O(n^2) 가 되겠지만 실제로 두번째 for는 검사하려는 숫자의 제곱근부터 검사하기 때문에 평군시간복잡도를 구하면 O(n^2)보다 떨어질것이라 추측한다.
이 외에도 에라토스테네스의 체를 이용하는 방법이 있다.
- 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
- 2는 소수이므로 오른쪽에 2를 쓴다.
- 자기 자신을 제외한 2의 배수를 모두 지운다.
- 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다.
- 자기 자신을 제외한 3의 배수를 모두 지운다.
- 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다.
- 자기 자신을 제외한 5의 배수를 모두 지운다.
- 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.
출처 : 위키백과
이를 이용하면 더욱 빨리 구할 수 있다.
웹에서 다른사람이 만든 코드를 인용하겠다.
