백준 1929번 C언어 소수구하기 - 성공

전에풀었던 코드

처음에는 시간복잡도를 줄이기 위해서 if문의 break point를 줄이는 방식에 대해 찾아봤는데, 이것으로 시간을 줄이기 보다 반복적인 연산을 줄이는 것이 중요하다고 생각이 들어 위키피디아에 소수구하는 방식에 대해 검색을 했다.

if문잘사용하는방법

소수구하는방법

그러다가 확률론적으로 구하는 방법, 좀 더 간단한 방법 등등 찾게 됐는데 에라토스테네스의 체를 사용한 방법이 가장 간단하고, 시간을 많이 잡아먹지도 않고, 직전 포스트에서 내가 생각했던 방식과 유사해서 이것을 사용해 보기로 했다.

1. 배열에 한번 소수인지 아닌지 정해두고(0,1로 표현)
2. m,n범위를 정해서 그 숫자가 0이면 print, 1이면 넘어가는 형식

위의 그림을 보면 이해가 쉽다. 2가 들어왔으면, 4, 6, 8, 10 .. 이런식으로 그 소수는 소수가 아니고, 3이 들어왔으면 6, 9, 12 .. 이런식으로 소수가 아니다. 이는 nested loop을 사용하면 간편하게 풀 수 있을 것이다.

#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;
}

참고1
참고2