[Coding test Basic with c++] 모두의 약수

문제

자연수 N이 입력되면 1부터 N까지의 각 숫자들의 약수의 개수를 출력하는 프로그램을 작성하 세요.
만약 N이 8이 입력된다면 1(1개), 2(2개), 3(2개), 4(3개), 5(2개), 6(4개), 7(2개), 8(4 개) 와 같이 각 숫자의 약수의 개수가 구해집니다.
출력은 다음과 같이 1부터 차례대로 약수의 개수만 출력하면 됩니다.
1 2 2 3 2 4 2 4 와 같이 출력한다.

▣ 입력설명
첫 번째 줄에 자연수 N(5<=N<=50,000)가 주어진다.

▣ 출력설명
첫 번째 줄에 1부터 N까지 약수의 개수를 순서대로 출력한다.

 

입력예제

8

 

출력예제

1 2 2 3 2 4 2 4

 

처음에 푼 풀이(시간 초과)

#include<stdio.h>
using namespace std;

int main(){
	// 모두의 약수 - 제한시간 1초 

	int a, i , j, cnt;
	scanf("%d",&a);

	for(i=0; i < a; i++){
		for(j=0; j < i; j++){
			if(a%j==0) cnt++;
		}
		printf("%s",&cnt);
		cnt = 0;
	}
		
	
   	return 0;
    
}

각 약수들의 개수를 출력하면 되는 거기때문에 처음에 이중 for문에 자연수 N값에 대해 N번의 자연수로 나누어서 약수의 개수들을 각 각 출력했다. 하지만 이중 for문으로 시간복잡도가 n의 제곱이라 시간 초과로 오답처리 되었다. 

시간 초과가 안되게 하려면 , 다르게 생각해보기로 했다. 

 

 

풀이

#include<stdio.h>
using namespace std;

int cnt[50001]; 

int main(){
	// 모두의 약수 - 제한시간 1초 

	int n, i , j;
	scanf("%d",&n);
	
	for(i=1 ; i<=n ;i++){
		for(j=i; j<=n; j=j+i){  //1의배수,2의배수,3의배수... 
			cnt[j]++;
		}
	}
	
	for(i=1 ; i<=n ;i++){
		printf("%d",cnt[i]);
	}

   	return 0;
    
}

cnt라는 배열에 각 자연수들의 배수만 개수를 플러스 시켜서 담아낸다.

cnt[50001] = [ 2의 배수의 cnt 증가, 3의 배수의 cnt 증가, 4의 배수 cnt 증가... ] 이렇게..

그럼 각 배수들만 for문으로 체크 하기 때문에 시간복잡도가 줄어들게 된다.