백준 11653번 C언어

문제푼 시간 : 10시 19분 ~ 10시 34분 (15분)

1. 1,2,3,4,5... 10,000,000 까지 하나씩 늘려가면서 주어진값을 %연산자를 이용해서 0이 나오는값이 소인수라고 생각했다. -> N까지로 변경해도 될 것이다고 코딩하며 생각함.
2. 예를들어 10이라는 숫자가 들어왔을때 2부터 2로 나머지연산을 사용해 보고, 만약 맞다면 나머지 연산으로 나온 값을 다시 나머지 연산을 사용해야 겠다고 생각했다. -> 여기서 break해주면 시간을 줄여주겠지.
3. 반복적으로다시 나머지 연산을 사용하는건, recursive하게 하면 편할것이고, time complexity가 늘어나겠지만 해보고 확인해봐야겠다.

#include <stdio.h>

int calculate(int n) { // 포인터를 사용하는게 더 빠를 것 같긴한데 일단은 call by value로
	int i, bool_check = 0;
	for (i = 2; i <= n; i++) {
		if (n % i == 0) {
			bool_check = 1;
			break;
		}
	}
	if (bool_check == 0) return -1;
	return i;
}

int main(void) {
	int N;
	int sum;
	int temp = 1;
	int temp_index;
	
	scanf("%d", &N);

	while (1) {

		temp_index = calculate(N);

		if (temp_index != -1) {
			printf("%d\n", temp_index);
		}

		N /= temp_index;


		if (N == 1)break;
	}

}

풀다보니까 recursive하게 할 필요없이 index를 기준으로해서 다시 나누어준다면 빠르게 진행 할 수 있다고 생각이 들었고, 수정했다.

bool_check이라는 함수는 한번이라도 "%"연산자가 사용된게 있는지 확인했고, 그런게 없다면 -1을 리턴하게해서 그런 수는 표출되지 않게 했다.