[인프런 C++] 9. 모두의 약수 (제한시간 1초)

자연수 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이 주어진다.

8

 

출력

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

1 2 2 3 2 4 2 4

 

1트 (성공)

약수 모두 찾기 (제한시간에 걸림) => 시간복잡도 n^2

#include <iostream>
using namespace std;

int main(){
	//freopen("input.txt", "rt", stdin);
	int a, cnt = 0;
	cin >> a;
	
	for(int i = 1; i <= a; ++i){
		cnt = 0;
		
		for(int j = 1; j <= i; ++j){
			if(i % j == 0){
				cnt++;
			}
		}
		
		cout << cnt << ' ';
	}
	
	return 0;
}

 

 

2트 (강의 풀이)

배열을 생성하여, 약수가 1부터 n까지 돌면서 약수에 해당하는 수에 ++를 해주어서 구하는 방법

j = j + i씩 증가하면서 이중 for문을 돌기 때문에 for문을 도는 횟수가 확연히 줄어든다. (데이터가 클수록 더더욱)

시간복잡도 => 거의 nlogn

 

i = 1, j = 1 2 3 4 5 6 7 8

i = 2, j = 2 4 6 8

i = 3, j = 3 6

i = 4, j = 4

#include <iostream>
using namespace std;

int main(){
	//freopen("input.txt", "rt", stdin);
    int cnt[50001];
	int n;
	cin >> n;
	
	for(int i = 1; i <= n; ++i){
		for(int j = i; j <=n; j=j+i){
			cnt[j]++;
		}
	}
	
	for(int i = 1; i<=n; ++i){
		cout << cnt[i] << ' ';
	}
	
	return 0;
}

 

개념

둘 다 이중for문을 사용