3131. 100만 이하의 모든 소수(D3)

소수인지 판별하기 위해 1~100만까지 반복문을 돌리며

미리 구해놓은 소수로 나누어 떨어지는지 확인하였다.

나누어 떨어지지 않으면 소수이다.

이방법으로 약 142ms 가 걸렸다고 나왔는데, 다른사람들은 20ms정도도 나온다. 어떻게 구현했는지 궁금하다.

#include <stdio.h>
#include <math.h>
int arr[500000] = { 2,3,5,7, };
int cnt = 4;
int main(void) {
    printf("2 3 5 7");
    for (int i = 11; i<1000000; i++) {
        int check = 0;
        for (int j = 0; j < cnt; j++) {
            if (i%arr[j] == 0) {
                check = 1;
                break;
            }
            else if (arr[j] > sqrt(i) ) {
                break;
            }
        }
        if (check == 0) {
            arr[cnt] = i;
            cnt++;
            printf(" %d", i);
        }
    }
    return 0;
}