190719_소수구하기_C

에라토스테네스의 체를 사용할 때와 아닐 때, 시간 복잡도를 비교해보았다.

무려 소요 시간이 10배 차이가 난다. (2번의 코드 길이가 더 긴 이유는 1번을 주석 처리해서이다.)

 

1. 제곱근을 사용해서 풀었을 때

2. 에라토스테네스의 체를 사용해서 풀었을 때

#include <stdio.h>

int main(void) {

    int m;
    int n;
    scanf("%d %d", &m, &n);

    //에라토스테네스의 체
    int arrange = n-m+1;
    int notSosu[1000000] = {0,};

    notSosu[1] = 1;
    for ( int i=2; i<=n; i++ ) {
        if ( notSosu[i] == 0 ) {
            for ( int j=i; j<=n; j+=i ) {
                if ( i != j ) {
                    notSosu[j] = 1;
                }
            }
        }
    }

    for ( int i=m; i<=n; i++ ) {
        if ( notSosu[i] == 0 ) {
            printf("%d\n", i);
        }
    }
    
    return 0;
 }