[Algorithm] 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(5<=N<=50,000)가 주어진다.

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

입력

8

출력

1 2 2 3 2 4 2 4

 

모두의 약수 코드 : 시간 제한 없음

가장 생각하기 쉬운 코드가 아닐까 한다.

for문을 n까지 돌고 내부 for문에서 1부터 i까지 순회하며 i의 약수를 계산하고 출력한다.

코드는 간결하지만 n의 값이 커지면 내부 for문도 n회에 근사하게 반복한다.

따라서 시간 복잡도가 O(N^2)으로 N의 증가에 따라 실행될 명령어 수가 기하급수적으로 증가하게 된다. 

#include <iostream>

using namespace std;

int main()
{
	int n, count;

	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		count = 0;

		for (int j = 1; j <= i; j++)
		{
			if (i % j == 0) count++;
		}

		cout << count << " ";
	}
}

모두의 약수 코드 : 시간 제한 있음

약수의 개념을 활용한 코드이다.

1은 모든 수의 약수이다. 2는 2 4 6 8... 의 약수이다. 3은 3, 6, 9, 12의 약수이다. 바로 이 개념을 코드로 옮긴 것이다.

 

n이 8이 입력되면 길이 9의 벡터를 정의한다.(0은 사용 안 함)

 

i가 1일 때 내부 for문을 살펴보면 vec[1]++; vec[2]++;... vec[8]++; 까지 반복한다.

i가 2일 때 내부 for문을 살펴보면 vec[2]++; vec[4]++; ... vec[8]++; 까지 반복한다.

이처럼 i가 8까지 반복하게 되면 모든 수의 약수를 구하게 되는데 이전 코드보다 효율적으로 약수의 개수를 계산할 수 있게 된다.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n, count;

	cin >> n;

	vector<int> vec(n + 1);

	for (int i = 1; i <= n; i++)
	{

		for (int j = i; j <= n; j += i)
		{
			vec[j]++;
		}
	}

	for (int i = 1; i <= n; i++)
		cout << vec[i] << " ";

	return 0;
}