BOJ 백준온라인져지 1037 약수 풀이

N은 약수의 처음 주어진 숫자와 마지막 숫자를 곱해주면 나온다.

예를 들어 9가 N이면

3 이 약수로 있다.

그러면 3 * 3 = 9

20 이면

2 4 5 10

2 * 10 = 20 

	#include <cstdio>
	#include <vector>
	/**
	* https://www.acmicpc.net/problem/1037
	* BOJ 백준온라인져지 1037 약수 풀이
	*/
	using namespace std;
	vector<int> divisor;
	void quickSort(int l, int r){
	int i = 0, j = r;
	int pivot = divisor[(l + r) / 2];
	do{
	while(divisor[i] < pivot) i++;
	while(divisor[j] > pivot) j--;
	if(i <= j){
	int temp = divisor[i];
	divisor[i] = divisor[j];
	divisor[j] = temp;
	i++, j--;
	}
	}while(i <= j);
	if(l < j) quickSort(l, j);
	if(r > i) quickSort(i, r);
	}
	int main(){
	int N;
	scanf("%d", &N);
	while(N--){
	int temp;
	scanf("%d", &temp);
	divisor.push_back(temp);
	}
	quickSort(0, divisor.size()-1);
	printf("%ld", (long) divisor[0] * (long) divisor[divisor.size()-1]);
	}

view raw BOJ_1037.cpp hosted with ❤ by GitHub

20 은 2 * 2 * 5 로 소인수 분해가 된다.

2 와 10