【数学】素因数分解
Posted: 2012年1月26日(木) 23:35
twitterの方で話題になったので素因数分解をしてくれるプログラムを作ってみました
・・・が、適当に作ったからか、ある程度数が大きくなると固まるという現象が発生しています。
とりあえずソースを
素数判別の所と分解の所はほとんど同じ処理してるからなんとか併せて書けそうですが・・・
追記
処理に無駄があったと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の方で言われたので直しました。