【数学】素因数分解

みなさん、学校などで習ったことをプログラムにしてみませんか?
プログラムの勉強にも、習ったことの復習にもなって一石二鳥かもしれません。
自分が投稿しまくるだけになったらすみません...
フォーラム(掲示板)ルール
トピック名はなるべく
[b]【教科/科目名】簡単な内容[/b]
の形にしてください。
重複したトピックはなるべく作らないよう気をつけてください。
(重複した内容を投稿したい時は返信の形でお願いします。
重複したからといって削除や移動は原則として行いません)
コードは正しくcodeタグで囲みましょう。
プログラミングの授業の内容ををそのままや移植して投稿するのはご遠慮ください。
間違っていたら返信で指摘してあげてください。
返信
アバター
ぱにしん
記事: 58
登録日時: 8年前
住所: 滋賀

【数学】素因数分解

#1

投稿記事 by ぱにしん » 7年前

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
記事: 6216
登録日時: 8年前
住所: 千葉県
連絡を取る:

Re: 【数学】素因数分解

#2

投稿記事 by みけCAT » 7年前

i<Num/2ではなくi*i<=Numでいいのではないでしょうか?
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
ぱにしん
記事: 58
登録日時: 8年前
住所: 滋賀

Re: 【数学】素因数分解

#3

投稿記事 by ぱにしん » 7年前

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

返信

“習ったことをプログラムで表してみよう!” へ戻る