[C++] 해밍 수 (Hamming Number)

숙제 1 (해밍 수)

해밍 수 (Hamming Number) 는 소수 2, 3, 5 이외의 다른 소수를 약수로 가지지 않는 자연수를 말한다. 예를들면, 60은 소수 2, 3, 5 이므로 해밍수이다. 그러나 42는 소수 7로 나누어지므로 해밍 수가 아니다.

<규칙>

해밍수를 가장 작은 수인 1부터 점점 큰 수 순서로 나열하는 방법은 다음과 같은 아이디어를 사용하여 구할 수 있다.

1. 자연수 1은 해밍수이다.

2. H가 해밍수이면, 2H, 3H, 5H도 또한 해밍수이다.

3. 다음으로 큰 해밍수를 계산하기 위해서는,이전에 만들어진 해밍수들의 2배, 3배, 5배수들 중에서 아직까지 선택되지 않은 수 중에서 가장 작은 것을 선택한다.

해밍수를 가장 작은 수인 1부터 점점 큰 수 순서로 나열할때, k-번째 해밍수를 계산하는 프로그램을 작성하시오.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;


int main(){
	vector<unsigned long long> arr;
	arr.push_back(1);
	int num=0x00;
	cin>>num;
	int i=0;
	while(i<num){
		arr.push_back(arr[i]*2);
		arr.push_back(arr[i]*3);
		arr.push_back(arr[i++]*5);
		sort(arr.begin(), arr.end()); 
		arr.erase(unique(arr.begin(),arr.end()),arr.end());
	}
		
	cout<<arr[num-1]<<endl;
	
	return 0;
}