【数学】素因数分解

[ぱにしん]

twitterの方で話題になったので素因数分解をしてくれるプログラムを作ってみました
・・・が、適当に作ったからか、ある程度数が大きくなると固まるという現象が発生しています。
とりあえずソースを

コード:

#include<iostream>
#include<vector>

using namespace std;

int PrimeHanbetu(int Num){
	for (int i=2; i<Num/2; i++){	
		if(Num%i == 0){		
			return 1;		
		}	
	}
	return 0;
}



int main(void){
	int num;
	int MaxPrime=2;
	vector<int> PrimeList;
	
	cout << "数字を入力→";
	cin >> num;

	while(PrimeHanbetu(num)==1){
		for (int i=MaxPrime; i<num/2; i++){		
			if(num%i == 0){
			
				PrimeList.push_back(i);
				num = num/i;
				MaxPrime = i;
				break;

			}		
		}
	}



	//最後に残った素数を記録	
	PrimeList.push_back(num);


	for(int j = 0; j<PrimeList.size(); j++){		
		cout << PrimeList[j] << endl;
	}
	return 0;
}

素数判別の所と分解の所はほとんど同じ処理してるからなんとか併せて書けそうですが・・・

追記
処理に無駄があったとtwitterの方で言われたので直しました。

[みけCAT]

i<Num/2ではなくi*i<=Numでいいのではないでしょうか？

[ぱにしん]

みけCATさん＞
なるほど・・・そういう方法があったんですね。
その辺の無駄を省くために「総当たりよりはマシ」と思ってそうしたんですが。
そこまで考えが及ばないのは経験不足なのか、私の考えが足りてないのか・・・