素因数分解 - 秋田大学ICPC対策室@wiki

素因数分解

説明を書くのが面倒くさいので、とりあえずソースコードだけ載せておきます。
小さい数なら問題なく分解できるはずです。

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

//素因数分解
vector<int> f(int x){
	int d=3, q;
	vector<int> vc;

	while( x >= 4 && (x % 2) == 0 ){
		vc.push_back( 2 );
		x /= 2;
	} 
	q = x / d;
	while( q >= d ){
		if( (x % d) == 0 ){
			vc.push_back( d );
			x = q;
		}else{
			d += 2;
		}
		q = x / d;
	}
	vc.push_back( x );
	return vc;
}

int main(){
	int x;
	vector<int> vc;
	while( cin >> x , x ){
		vc.clear();
		vc = f(x);
		cout << x << " = " ;
		for(int i=0 ; i<vc.size() ; i++){
			cout << vc[i] << "";
			(i==vc.size()-1)? cout << endl : cout << " * ";
		}
	}
}

...