모두의 약수 (시간 제한 1초) C++

n 을 입력하면 1 부터 n까지의 정수의 약수를 각각 구한다.

만약 이것을 각각의 정수에 for문을 돌린다면, 무조건 시간 초과가 발생한다.

이것을 막기 위해 다른 방법의 알고리즘을 사용한다.

 

8을 입력했을 때 numArr는 아래와 같이 초기화된다.

1	2	3	4	5	6	7	8
0	0	0	0	0	0	0	0

1을 약수로 갖는 수를 체크한다. 이런식으로 2의 배수를 다시 체크하고, 3의 배수를 체크한다. 

이렇게 i 가 num으로 갈 때까지, for문을 돌려서 i를 약수로 갖는 값(j)을 찾아 numArr에서 카운팅한다.

j 는 i 보다 작을 수 없으니까 j = i 부터 시작하여 실행 속도를 높힌다.

 

#include<stdio.h>

int main() {
	int num;
	scanf("%d", &num);
	int numArr[50001] = { 0 };
	int i, j;
	for (i = 1; i <= num; i++) {
		for (j = i; j <= num; j = j + i) {
			if (j%i == 0) {
				numArr[j] ++;
			}
		}
	}
	for (i = 1; i <= num; i++) {
		printf("%d ", numArr[i]);
	}
}