2008年12月28日

素因数分解するプログラム

任意の数(1000)の素因数分解を行うプログラムをいろいろあって作ることになったりしました。

//任意の数字を素因数分解するプログラム

#include<stdio.h>

#define MAX 1000 //限界値

typedef struct Data{ //素数格納データ
int num[MAX];
int count;
}Data;

Data generatePrime(Data data);
void primeDecomposition(int buf, Data data);

int main(){

Data data = {0};
int buf;

data = generatePrime(data); //素数を求める

scanf("%d", &buf);
if(buf > 1000 || buf <= 0){ //エラー処理
printf("input error\n");
return -1;
}

primeDecomposition(buf, data); //素因数分解する

return 0;
}

Data generatePrime(Data data){

int i, limit = 2;
int flag = 0;

while(limit != MAX){
for(i = 2; i < limit; i++){
if(limit % i == 0)flag = 1;
}
if(flag == 0)data.num[data.count++] = limit;
else flag = 0;
limit++;
}

return data;
}

void primeDecomposition(int buf, Data data){

int i;

while(1){
for(i = 0; i < data.count; i++){
if(buf % data.num[i] == 0){
printf("%d ", data.num[i]);
buf /= data.num[i];
break;
}
}
if(buf == 1)break;
else printf("* ");
}

}


C言語で書くのは当たり前すぎたので、ついでにC++の勉強をかねて書いてみました。


//任意の数字を素因数分解するプログラム
#include<iostream>
#include<vector>
using namespace std;

class Data{
private:
vector<int> vec; //vectorクラス
int count;
int limit;
void generatePrime();

public:
Data(int buf){
count = 0;
limit = buf;
generatePrime();
}
void primeDecomposition();
void printData();
};

void Data::generatePrime(){

int lim = 2;
bool flag = false;

while(lim != limit){
for(int i = 2; i < lim; i++){
if(lim % i == 0)flag = true;
}
if(!flag)vec.push_back(lim); //末尾に要素追加
else flag = false;
lim++;
}

}

void Data::primeDecomposition(){

int b = limit;

while(true){
for(vector<int>::iterator v = vec.begin(); v != vec.end(); v++){
if(b % *v == 0){
cout << *v;
b /= *v;
break;
}
}
if(b == 1)break;
else cout << " * ";
}

}

void Data::printData(){

for(vector<int>::iterator v = vec.begin(); v != vec.end(); v++){ //イテレータを用いる
cout << *v << endl;
}

}

int main(){

int buf;

cin >> buf;
if(buf <= 0){ //エラー処理
cout << "input error\n" << endl;
return -1;
}

Data data(buf);

data.printData(); //bufまでの素数を表示する
data.primeDecomposition(); //素因数分解する

return 0;
}


C言語のほうは配列でとっているので、限界値が定められています。リスト構造を使えば限界値はなくなりますが、めんどうだったのでやらなかったです。

C++のほうはテンプレートクラスであるvectorクラスを使って実現してみました。動的配列と言われるだけあって難なく限界値なしにできました。

やっぱC++おいしいです。
今回のプログラムを書いて僕自身まだまだ知識が足りないと感じました。

もっと2月からもっとC++勉強したいな・・・。でも、Javaも勉強したいとも思ってます。
今やってるバイトで稼いだお金でパソコン買って本格的なサーバ構築もやってみたい・・・とかも思ってます。

ほんと・・・やりたいことが多すぎる><


最後についでに実行例をはっておきます。
=>1024
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
101
103
107
109
113
127
131
137
139
149
151
157
163
167
173
179
181
191
193
197
199
211
223
227
229
233
239
241
251
257
263
269
271
277
281
283
293
307
311
313
317
331
337
347
349
353
359
367
373
379
383
389
397
401
409
419
421
431
433
439
443
449
457
461
463
467
479
487
491
499
503
509
521
523
541
547
557
563
569
571
577
587
593
599
601
607
613
617
619
631
641
643
647
653
659
661
673
677
683
691
701
709
719
727
733
739
743
751
757
761
769
773
787
797
809
811
821
823
827
829
839
853
857
859
863
877
881
883
887
907
911
919
929
937
941
947
953
967
971
977
983
991
997
1009
1013
1019
1021
2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2
posted by たこ at 05:36 | Comment(2) | TrackBack(0) | プログラミング
この記事へのコメント
  1. 相当久々にのぞいたらC言語ブログにナットル( ゚д゚)
    大学のお勉強頑張ってくだされ
    Posted by ノータコ、ノーナナシ at 2009年01月26日 00:13
  2. VIPのスレをまとめる時間がとれなくて・・・。
    申し訳ないです・・・><
    Posted by たこ at 2009年01月27日 17:07
コメントを書く(過剰なエロネタはアウアウ!)
お名前:

メールアドレス:

ホームページアドレス:

コメント:

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。

この記事へのトラックバック
×

この広告は1年以上新しい記事の投稿がないブログに表示されております。