소인수분해 하는 방법

임의의 실수 x에 대하여 factorize 하는 방법

 

[2, N^(1/2)] 의 수들로 나눠 볼 때 나누는 수가 소수인지 확인할 필요가 없다!!!

 

만약에 N이 2로 나눠 떨어진다면 N값을 2로 나눠서 다시 2로 나눠 떨어지는지를 확인하고 그렇지 않은 경우 3으로 나눠 떨어지는지 확인하고 ... 반복한다.

 

이 과정을 반복하면 소수가 아닌 인수는 자연스럽게 없어지는 것을 확인할 수 있다. 

 

따라서 Time Complexity O(N^(1/2)) 이 나온다.

 

factorize 하는 코드

 

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'
#define ll long long

using namespace std;

bool primality_test(int x) {
	if(x==1) return false;
	for(int i=2; i*i<=x; i++) {
		if(x%i==0) return false;
	}
	return true;
}

vector<int> factorize(int x) {
	vector<int> ret;
	for(int i=2; i*i<=x; i++) {
		while(x%i==0) {
			ret.push_back(i);
			x/=i;
		}
	}
	if(x>1) ret.push_back(x);
	return ret;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	for(int i=1; i<=1000; i++) {
		vector<int> v = factorize(i);
		if(v.size()==0) continue;
		cout<<i<<"'s factorization : ";
		for(int i=0; i<v.size(); i++) {
			if(i!=v.size()-1) cout<<v[i]<<"x";
			else cout<<v[i]<<endl;
		}
	}
	

	return 0;
}