2023.01.10 Baekjoon1929

https://www.acmicpc.net/problem/1929

코드 #1

#include<stdio.h>

int main(void) {
    int M,N;

    scanf("%d %d", &M, &N);

    if(M == 1) {
        M++;
    }

    for(int i=M; i<=N; i++) {
        int count = 0;
        for(int j=1; j<=i; j++) {
            if(i % j == 0) {
                count++;
            }
        }
        if(count == 2) {
            printf("%d\n", i);
        }
    }
}

코드는 정상적으로 작동이 되는데 백준에서 실행하면 계속 시간초과란 결과가 나온다. 질문게시판을 보니 에라토스테네스의 체란 알고리즘을 사용하여 시간복잡도를 줄여 푸는 문제인듯 하다.

에라토스테네스의 체란
대량의 소수를 빠르게 구하는 알고리즘으로 배열을 생성하여 소수가 아닌 수들을 지워나가 소수들만으로 채워진 배열을 이용하는 방식을 취한다.

#include<stdio.h>

int main(void) {
    int M,N;
    int prime[1000001] = {0};
    int number = 1000000;

    scanf("%d %d", &M, &N);

    for(int i=2; i<=number; i++) {
        prime[i] = i;
    }

    for(int i = 2; i<=number; i++) {
        if(prime[i] == 0) {
            continue;
        }
        for(int j=2; j<=number; j++) {
            prime[i*j] = 0;
        }
    }

    for(int i=M; i<=N; i++) {
        if(prime[i] != 0) {
            printf("%d\n", prime[i]);
        }
    }
}

에라토스테네스의 체를 이용하여 코드를 작성하였는데 Runtime error가 출력됐다.

for(int i = 2; i<=number; i++) {
    if(prime[i] == 0) {
        continue;
    }
    for(int j=2; j<=number; j++) {
        prime[i*j] = 0;
    }
}

문제는 위 이중 반복문의 조건인데, 맨 처음 2의 배수를 0으로 초기화하는데 이는 초기화 과정과 겹쳐 비효율적이며 옳지 못한 조건이다.

for(int i = 2; i<=number; i++) {
    if(prime[i] == 0) {
        continue;
    }
    for(int j=2*i; j<=number; j+=i) {
        prime[j] = 0;
    }
}

따라서 위와 같이 수정하는 것이 올바르다.