https://codejin.tistory.com/31
이 문제를 풀고 난 후에, 에라토스테네스의 체 알고리즘이 더 효율적이라고 조언을 받았다. 그래서 이 알고리즘으로 다시 풀어보았다.
에라토스테네스의 체는 소수를 찾는 하나의 알고리즘인데, 2부터 시작하여, 2의 배수를 모두 지운다. 그리고 1을 더한 3의 배수들도 지운다. 또 1을 더하면 4가 되는데, 아까 2의 배수들이 모두 지워졌으므로, 무시하고 다시 1을 더한다. 이를 반복하여 지워지지 않은 숫자들의 배수를 모두 지워가면서 소수를 찾는 방법이다.
이를 적용하여 다음과 같이 다시 풀어보았다.
#include <stdio.h>
#include <stdbool.h>
#define SIZE 1000001
int main () {
bool seive[SIZE] = {false, false}; // 0부터 시작 (0,1,2,3....), 0은 계산의 편의성을 위해 넣음, 1은 소수도 합성수도 아니므로 false
int m,n;
scanf("%d%d", &m, &n);
for (int i = 2; i < SIZE; i++) {
seive[i] = true; // 일단 2 이상의 모든 숫자들을 true로 초기화
}
for (int i = 2; i < SIZE; i++) {
if (seive[i]) { // 만약 지워지지 않은 숫자라면
for (int p = 2; p*i < SIZE; p++) {
seive[i*p] = false; //그 배수들을 모두 지운다
}
}
}
for (int i = m; i <= n; i++) {
if (seive[i]) printf("%d\n", i);
}
return 0;
}
'coding_test > BAEKJOON' 카테고리의 다른 글
백준 4153번 C언어 풀이 (0) | 2021.08.24 |
---|---|
백준 1978번 C언어 풀이 (0) | 2021.08.24 |
백준 1929번 C언어 풀이 (0) | 2021.08.23 |
백준 1259번 C언어 & Python3 풀이 (0) | 2021.08.23 |
백준 1085번 C언어 풀이 (0) | 2021.08.22 |