[백준] 1929 소수 구하기

문제 : M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

소수를 구하는 알고리즘은 여러 가지가 있습니다.

하지만 이 문제는 2초라는 시간제한이 있습니다. 그렇기 때문에 가장 효율적인 알고리즘을 채택해야 합니다.

예를 들어 수 하나(n)가 주어졌을 때 2부터 (n-1) 까지 나누어 본다 하면 연산횟수는 n-2 번이 될 것입니다.

하지만 나오는 수마다 일일이 계산한다면 연산은 배로 많아질 것이고, 이는 효율적이지 못합니다.

 (실제로 일일이 계산하면 시간초과가 뜬다)

에라토스테네스의 채를 이용합니다. 이 알고리즘을 사용하면 시간복잡도를 줄일 수 있습니다.

2를 제외한 2의 배수를 삭제, 3을 제외한 3의 배수를 삭제... 이런 식으로 나아가면 소수만 남게 됩니다.

수가 여러개 주어졌을때도 배열에 저장만 해 둔다면 한번만 계산 해두면 다시 꺼내 쓸 수 있죠.

이걸 이용해서 코드를 짜 보았습니다.

#include <stdio.h>
 
int arr[1000001]={1,1,1,};
 
int main()
{
    int min,max,temp;
    scanf("%d %d",&min,&max);
    for(int i=2;i<=max;i++)
    {
        temp=i;
        while(temp+i<=max)
        {
            temp=temp+i;
            if(arr[temp]!=1)
            {
                arr[temp]=1;
            }
        }
    }
    
    if(min<=2&&max>=2)
    {
        printf("2\n");
    }
    
    for(int i=min;i<=max;i++)
    {
        if(arr[i]==0)
        {
            printf("%d\n",i);
        }
    }

    return 0;
}