【C++】素因数分解プログラムと処理時間計測【chronoライブラリ】
意外にもスパンが短く、5日ぶりです、ふくともです。
今回は、書こうと思ったものの先に前回の記事を書くべきだと思い一旦流した記事を。
なんとなくノリで作ってみたプログラムを晒してみます(実用性は気にしない)
作ったものはタイトル通り素因数分解プログラムで、入力された2以上の整数値を素因数分解します。
vectorの使い方については前回の記事で触れたため割愛します。
流れとしては
Ⅰ. 値入力
Ⅱ. 与えられた値を構成する素数の検索
Ⅲ. Ⅱで得た各素数の指数を計算
Ⅳ. 出力
です
性能テストのために処理時間も計測しています(が実用性は気にしないなら不要な気も)
以下コード(コメントも一応添えていますが解説は後述)
#include <iostream>
#include <vector>
#include <chrono>
using namespace std;
// 素数と指数をペアで格納する構造体を定義
struct KEKKA{
int Sosuu;
int Shisuu;
};
int main(void)
{
int N;
cout << "2 ≦ N=";
cin >> N;
cout << endl;
// 入力が終わったタイミングで計測スタート
auto start=chrono::system_clock::now();
if(N<=0){
cout << "ERROR";
}else if(N==1){
cout << "1^1";
}else{
// 変数宣言とか
vector<int> sosuu;
sosuu.push_back(2);
vector<kekka> kekka;
// Nを構成する素数の取得
// エラトステネスの篩
// 3以上の素数は奇数であることを利用
for(int i=3;i<=N;i+=2){
if(N%i==0){
bool flg=true;
for(int j=0;j<sosuu.size();++j){
if(i%sosuu[j]==0) flg=false;
}
if(flg==true) sosuu.push_back(i);
}
}
// 求めた各素数の指数を求める
for(int i=0;i<sosuu.size();++i){
int M=N;
int shisuu=0;
for(;M%sosuu[i]==0;++shisuu){
if(M%sosuu[i]==0)
M/=sosuu[i];
}
KEKKA tmp={sosuu[i],shisuu};
kekka.push_back(tmp);
}
// 出力
cout << N << " = ";
for(auto p=kekka.begin();p!=kekka.end();++p){
if(p->Shisuu!=0){
cout << p->Sosuu << "^" << p->Shisuu;
// kekkaコンテナの最終要素でなければ「素数^指数」の後に「 * 」を出力
if(p!=kekka.end()-1) cout << " * ";
}
}
}
cout << endl;
auto end=chrono::system_clock::now();
auto diff = end-start;
auto diff_mcrsec = chrono::duration_cast<chrono::microseconds>(diff).count();
cout << "所要時間:" << diff_mcrsec << "マイクロ秒" << endl;
return 0;
}
chrono ←処理時間の計測などに使うライブラリ
chrono::system_clock::now() ←現在時刻の取得
→計測終了時から計測開始時を引くと処理時間が得られる
※型名が長いのでautoで指定したほうがタイプミスも少なくて無難
正式にはstd::chrono::system_clock::time_point型
chrono::duration_cast<chrono::microseconds>(diff).count() ←変数diffの値をマイクロ秒の整数値に変換
変換可能な単位などはこちらを参照↓
0以下の値が入力された場合にはERRORを出力
1が入力された場合には1^1を出力
2以上が入力された場合にはその値を素因数分解して出力
ex) 入力値:15 出力:3^1 * 5^1
最初のループではNの約数の内、素数であるものをsosuuコンテナに格納する
その次のループでは得た素数で入力値を割り、割り切れればその素数の指数を1増やす
割り切れなくなったらKEKKA構造体型の変数に素数と指数をペアで格納し、その変数をkekkaコンテナに格納する
↑格納するデータが一つでない場合には一度構造体型変数に纏めてからコンテナに格納するほうが楽
「入力値= 素数^指数 * 素数^指数 * 【中略】* 素数^指数」のフォーマットで出力
以上です。
プログラムそのものは置いておくとして、処理時間の計測はそこそこに有用だと思います。
2015年の記事は今回が最後になると思います、閲覧してくださった方々ありがとうございます。
それでは良いお年を。
2015/12/27 Sun.