백준2581, 소수

DP로 수행 시간 줄이려 했는데 머리가 안돌아가서 그냥 O(n^2) 의 브루트 포스.. 방식으로 작성

1은 소수가 아님

#include <stdio.h>
#define max_input   10003
#define nonPri      0
#define Pri         1
//arr[i] : 1부터 i까지의 사이의 합
int arr[max_input+1]={0,};
 
int main(void){
    int subNum = 0;
    int x= max_input;
    int M, N;
    int i=1;
    //initializing
    arr[1] = nonPri;
    for(i = 2; i<=max_input; i++){
        arr[i] = Pri;
    }
 
    for(i = 2; i<= max_input; i++){
        subNum = 0;
        for(int j = i+1; j<=max_input;j++){
            if(j%i==0 && arr[j]==Pri){
                arr[j] = nonPri;
                x--;
            }
        }
    }
 
    scanf("%d",&M);
    scanf("%d",&N);
    int sum=0;
    int min = 0;
    for(int i = M; i<=N; i++){
        if(arr[i] == Pri){
            sum+=i;
            if(min == 0){
                min = i;
            }
        }
    }
    if(sum==0){
        printf("-1\n");
        return 0;
    }
    printf("%d\n%d\n",sum, min);
    return 0;
}