소수를 찾을 때 사용한다.
- 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
- 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
- 자기 자신을 제외한 2의 배수를 모두 지운다.
- 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
- 자기 자신을 제외한 3의 배수를 모두 지운다.
- 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
- 자기 자신을 제외한 5의 배수를 모두 지운다.
- 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
- 자기 자신을 제외한 7의 배수를 모두 지운다.
- 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.
- 그림의 경우, 이므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.
M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.
// isPrime은 모두 1로 초기화되어 있는 상태.
isPrime[1] = 0; // (1은 소수가 아니다)
for (int i = 2; i*i <= N; i++) {
if (isPrime[i]) {
for (int j = i*i; j <= N; j += i) { // 해당 수를 배수로 가지는 수를 모두 소수가 아니라고 표시한다.
isPrime[j] = 0;
}
}
}
백준 1016 제곱 ㄴㄴ 수 - [풀이]
어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다.
제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고,
max보다 작거나 같은 제곱ㄴㄴ수가 몇 개 있는지 출력한다.
for (long long i = 2; i*i <= maxx; i++) {
ii = i*i;
if (minn%ii == 0) mm = minn;
else mm = (minn/ii+1)*ii;
for (long long j = mm; j <= maxx; j += ii) {
isNini[j-minn] = 0;
}
}