셀맨의 일상 블로그

소수를 구하는데 고대의 그리스 수학자 에라스토스테네스에 의하여 개발된 에라스토스테네스의 체(Sieve of Erastosthenes)라는 알고리즘이 있다. 이 알고리즘은 정해진 범위 안의 소수를 찾아주는 비교적 간단한 방법이다. 이 알고리즘은 정해진 범위만큼의 배열을 생성한다. 만약 sieve[i]의 값이 0이면 i는 소수라는 의미이고 sieve[i]가 1이면 소수가 아니다. 처음에는 모든 배열의 값이 0으로 초기화된다. 즉 처음에는 모든 정수가 소수라고 가정한다. 알고리즘은 가장 작은 소수인 i=2부터 시작한다. 상식적으로 2의 배수는 소수가 아닌 것이 확실하다. 정해진 범위 안에서 2의 배수를 모두 찾아서 sieve[] 값을 1로 만든다. 즉 2, 4, 6, 8, ... 등의 인덱스를 갖는 원소들은 모두 1로 설정된다. 다음에 i를 3으로 하나 증가시킨다. 다시 3의 배수(3, 6, 9, ...)를 찾아서 sieve[i]를 1로 만든다. i를 다시 하나 증가시키면 sieve[4]는 이미 1이므로 다음 i 값으로 넘어간다. sieve[i]가 0인 다음 i를 찾아서 i의 배수를 모두 1로 만든다. 정해진 범위에 대하여 이와 같은 절차를 완료한 후에도 0값을 가지는 원소는 소수가 된다. 이 알고리즘을 이용하여 2부터 100사이의 소수를 찾아보라.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

SIZE 상수의 값을 변환시키면 더 큰 범위까지의 소수를 구할 수 있다.

문제에서의 sieve[]가 a[]이다. i는 나누는 수, j는 나눠지는 수, k는 소수 아닌 것들을 거를 때 곱해주는 수이다.