[1929] 백준 : 소수구하기 (C)

출처 | https://www.acmicpc.net/problem/1929

문제

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

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

코드

//중첩 for문을 쓰면서 탐욕 탐색을 한다. [모든 경우의 수를 고려한다.]
//하나의 배열을 선언 [값은 문제에서 주어진 범위]
//그 범위에 맞게 배열을 선언 arr[10001] = {0,} <- 0으로 초기화 
// arr[1] = 1로 선언
// 이 배열에 소수의 값이 아닌 값을 인덱스에 저장한다. 
//[구현]
// 1. for(i = 2; i <= n; i++)
//		for(j = 2; i*j <= n; j++)
//				arr[i * j] = 1; 두개를 곱한 것을 1로 표시 트리에서 visited역할과 유사하다.
// 2. for(i = m; i<= n; i++)
//			if(arr[i] == 0)
//					printf("%d"
//


#include <stdio.h>
int main(void){
    int m,n,arr[1000001] = {0,};
    arr[1] = 1;
    
    scanf("%d %d", &m, &n);
    
    for(int i = 2; i <= n; i++){
        for(int j = 2; i * j <= n; j++){
            arr[i*j] = 1;
        }
    }
    
    for(int i = m; i <= n; i++){
        if(arr[i] == 0)
            printf("%d\n",i);
    }
    
    return 0;
}

느낀점 : cost가 많이 발생한다. 다른 방법을 모색해보자.