백준 2581번 C언어

상당히 지저분한 코드입니다. 개선점도 많아 밑의 참고 링크를 보는것을 추천드립니다

1. 직전 포스트에서 쓴 코드를 가져다가 쓰면 편할 것이라고 생각했다.
2. 배열을 담을 크기를 10001까지 만들고, M과 N 범위 안에있는 소수를 구하고 합하면 끝이다
3. 소수인데 M과 N의 범위사이에서 나올 수 있는 값은 처음 나온값이 가장 작은값이라서 min이라는 변수에 넣고, M과 N사이의 값을 sum이라는 변수에 넣고 한번이라도 넣었으면 q를 1로 설정해서 소수가 있다는 것을 표현함.

#include <stdio.h>

int main(void) {

	int a, b, array[10001] = { 0, }, array2[10001], c = 0, check_val, q = 0, min = 0, sum = 0,check_first = 0;
	
	scanf("%d %d", &a, &b);
	
	array2[c++] = 0;

	// 소수를 배열에 넣는 코드
	for (int count = 2; count < 10000; count++) {
		if (array[count - 1] == 0)
			array2[c++] = count;
		//	printf("%d ", count);

		for (int i = 0; i < 10000; i++) {
			if ((i + 1) % count == 0) {
				array[i] = 1;
			}
		}
	}

	// M과 N사이의 값을 sum이라는 변수에 넣고 한번이라도 넣었으면 q를 1로 설정해서 소수가 있다는 것을 표현함.
	for (int i = 0; i < c; i++) {
		if (array2[i] >= a && array2[i] <= b) {
			if (check_first == 0) {
				min = array2[i];
				check_first = 1;
			}
			sum += array2[i];
			q = 1;
		}
			
	}
	if (q == 0) {
		printf("-1");
	}
	else {
		printf("%d\n%d", sum, min);
	}

}

백준에서 돌렸을때 321ms가 나왔는데 시간 복잡도 측면에서 좋지 못하다.
쓸대없는 변수 선언이 많다.
nested loop으로 10000까지의 숫자를 사용하는것은 좋지 못하다.

---

해결법

1. 배열로 다 숫자를 직접 넣는 것이 아니라 index로만 사용해도 된다. (쓸대없는 변수선언 줄임)
2. 이중 for문에서 시작하는 index를 절반으로 줄여도 된다. 예를들어 2를 소수에서 제외했다면, 2의 배수부터는 포함 하지 않을 것이기 때문에 시작값을 절반(최소5000)으로 줄여도 상관없은 움직임일 것이다.
3. 이중 for문에서 안의 for문의 시작값을 count * i 로 변경한다. 왜냐하면, 소수니까 중복되는 값을 다시 채크 할 필요가 없으니까

참고