백준 1929

1929번: 소수 구하기 (acmicpc.net)

1929번: 소수 구하기

 

#include<stdio.h>

int main()
{
    int N=0, M=0;
    int flag=0;

    scanf("%d %d", &M, &N);
    
    for(int i=M; i<=N; i++)
    {
        if(i == 1)
            continue;

        flag = 0;
        for(int j=2; j<i; j++)
        {
            if(i % j == 0)
            {
                flag = 1;
                break;
            }
        }

        if(flag == 0)
            printf("%d\n", i);
    }

    return 0;
}
// 소수를 구하는 방법 중 가장 비효율적인 방법이라고 한다.

처음에 짠 코드. 직접 다 나눠서 나머지를 가지고 비교하는 방식으로 최대한 반복횟수를 줄인다고 break도 써보고 했지만 그럼에도 불구하고 시간초과로 실패했다.

 

구글링을 해보니까 직접 나눠서 하는 방식은 가장 비효율적이고, 소수를 구하는 방법중 "에라토스테네스의 체" 가 효율적이라는 것을 알게 되었다.

(시간복잡도에 대한 개념을 다시 공부해보면 좋을 것 같다. 가장 효율적인 소스코드를 짜는 방법과 함께...)

 

에라토스테네스의 체는 앞에서부터 2가 소수면 2의 배수는 모두 지우고, 3이 소수면 3의 배수는 모두 지우면서 쭉 끝까지 정리하는 방식이다.

참고: 백준 1929번 C언어 소수구하기 - 성공 (velog.io)

#include<stdio.h>

int main()
{
    int arr[100] = {0, };
    int N=0, M=0, cnt=0;

    arr[1] = 1;

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

    for(int i=2; i<=N; i++)
    {
        if(arr[i] == 1) // 이미 소수가 아니라면 과정 패스
            continue;
        
        cnt = 2;
        while(i*cnt <= N)   // N의 값보다 커질때 까지 반복해서 에라토스테네스의 체 구현
        {
            arr[i * cnt] = 1;   // 소수가 아니라면 1로 바꿔줌
            cnt++;
        }
    }

    for(int i=M; i<=N; i++)
    {
        if(arr[i] == 0)
            printf("%d\n", i);  // 최종적으로 0인 값, 즉 소수만 출력
    }

    return 0;
}
// 에라토스테네스의 체 (어짜피 범위만 보여주면 되니까 미리 배열을 만들어 놓고 출력만 함)

그래서 에라토스테네스의 체를 이용해서 짠 C코드.

에라토스테네스의 체를 이용하면 특정 범위 내의 소수를 출력시키기에는 좋으나, 어떤 수가 소수인가를 물어보는 프로그램에는 효율적이지 않을 것 같다.