Archive

For the アルゴリズム category

素数を求める~エラトステネスの篩 2~

No Comments

前回の[アルゴリズム]素数を求める~エラトステネスの篩~の改良版を作ってみた

前回作ったものは何も考えずにwikipediaさんに言われた通りそのままにやったのでやっぱり効率が悪かった。
しかも、ある数が素数かどうか調べるためにまたリストを走査しなきゃいけなかった。これは明らかに欠陥w

ってことでboolean配列にして添字の数が素数ならtrueとするようにした
こうするのが本当なんですよねきっとw


final int MAX = 1000000 + 1;
boolean[] primes = new boolean[MAX];
primes[2] = true;
for (int i = 3; i < MAX; i += 2) {
    primes[i] = true;
}
for (int i = 3; i * i < MAX; i += 2) {
    if (primes[i]) {
        for (int j = i * 2; j < MAX; j += i) {
            primes[j] = false;
       }
   }
}

やってることは前回と同じ
効率化のために2の倍数は最初から除外するようにした

前回のソースと今回のソースでどれだけ速度が違うかテストしてみました
100万までの素数を求めるまでの時間を計測
前回のと今回のを交互に実行、それぞれ合計11回繰り返し、一番遅かったものを除外
計10回の平均をとりました
これだけ繰り返してるとメモリの確保に時間がかかって大きな誤差が生まれるので
オブジェクト生成の時間は含めないことにしました

Test.java


import java.util.Iterator;
import java.util.LinkedList;
public class Test {
 public static void main(String[] args) {
  final int N = 10;
  long sum = 0, sum2 = 0;
  long time;
  long m = 0, m2 = 0;
  final int MAX = 1000000;
  System.out.println("t前回t改良版");
  for (int i = 1; i <= N+1; i++) {
   System.out.print(i + "回目t");
   System.out.print(time = eratosthenes(MAX));
   m = Math.max(m, time);
   sum += time;
   System.out.print("t");
   System.out.println(time = eratosthenes2(MAX));
   m2 = Math.max(m2, time);
   sum2 += time;
  }
  System.out.println("-------------------------");
  System.out.println("平均t" + (sum-m)/N + "t" + (sum2-m2)/N);
 }
 static long eratosthenes(int max) {
  LinkedList primes = new LinkedList();
  LinkedList numbers = new LinkedList();
  long time = System.currentTimeMillis();
  for (int i = 2; i <= max; i++) {
   numbers.add(i);
  }
  int prime;
  Iterator it;
  do {
   prime = numbers.getFirst();
   primes.add(prime);
   it = numbers.iterator();
   while (it.hasNext()) {
    if (it.next() % prime == 0)
     it.remove();
   }
  } while (numbers.getLast() > prime * prime);
  it = numbers.iterator();
  while (it.hasNext()) {
   primes.add(it.next());
  }
  return System.currentTimeMillis() - time;
 }
 static long eratosthenes2(int max) {
  int _max = max + 1;
  boolean[] primes = new boolean[_max];
  long time = System.currentTimeMillis();
  primes[2] = true;
  for (int i = 3; i < _max; i += 2) {
   primes[i] = true;
  }
  for (int i = 3; i * i < _max; i += 2) {
   if (primes[i]) {
    for (int j = i * 2; j < _max; j += i) {
     primes[j] = false;
    }
   }
  }
  return System.currentTimeMillis() - time;
 }
}

出力結果

前回	改良版
1回目	6309	20
2回目	6169	10
3回目	6209	10
4回目	6329	10
5回目	6349	10
6回目	6299	20
7回目	6339	10
8回目	6279	10
9回目	6299	20
10回目	6360	10
11回目	6449	10
-------------------------
平均	6294	12

違いすぎるw
前回のが効率悪すぎただけですねすいませんw

最大公約数~ユークリッドの互除法~

No Comments

今回は最大公約数を求めるアルゴリズム
ユークリッドの互除法とは、古代ギリシアの数学者ユークリッドさんが書いた『原論』の中に出てくるもので明示的に記述された最古のアルゴリズムらしいです
ちなみに、ユークリッドは英語名で本当はエウクレイデスだそうな
※エウクレイデス(Ευκλείδης (Eukleides),ラテン語名:Euclides,英語名:Euclid(ユークリッド)

さて、本題ですが、またwikipediaさんを引用w
2 つの自然数(または整式) a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。

うーん・・・なにを言っているのやら・・・w
さっぱりなので、もっと分かりやすく解説してみます(自分もいろんなとこを参考にしながらだからあってるかわからないけど・・・w)

a と b との最大公約数は b と r との最大公約数に等しいという性質 について
30と18をつかって考えてみます
30÷18=1あまり12 です これは
30=1×18+12 と書くことができます
この性質は30と18の最大公約数は18と12の最大公約数と同じと言っています
これは
30=1×18+12 から 18と12を割り切る数は30でも割り切れ、また
12=30-1×18 から 30と18を割り切る数は12でも割り切れるからです
割り切れる数をどれだけ足しても割り切れるってことですね

これをどんどん繰り返していきます
30と18の最大公約数
| |    30÷18=1あまり12
18と12の最大公約数
| |    18÷12=1あまり6
12と6の最大公約数
| |    12÷6=2あまり0
あまりが0になったときの除数、つまり6が最大公約数ということになります

わかりやすくなってないって・・・・・?w

これをアルゴリズムの手順として整理すると
1.二つの整数をa、bとする
2.b=0ならaを最大公約数として終了
3.a÷bのあまりをb、元のbをaとして2.にもどる

Javaで書くとこんな感じ

EuclidGCD.java


public class EuclidGCD{
    static int gcd(int a, int b){
    // b=0ならaを最大公約数として終了
        if(b == 0){
            return a;
        }else{
       // a÷bのあまりをb、元のbをaとして2.にもどる
            return gcd(b, a % b);
        }
    }

    public static void main(String[] args){    //aとbの最大公約数を求めます
        int a = 30;
        int b = 18;

        System.out.println(gcd(a,b));
    }
}

短い!w

ユークリッドの互除法は計算回数もかなり少なくてすむみたいで、
割って余りを取るという操作を、最悪でも小さい方の十進法での桁数の 5 倍繰り返せば、最大公約数に達する。(ラメの定理)
らしいです。1000桁の数なら5000回計算すれば求まるってことか はやw
素直に素因数分解してたらどれだけ時間がかかることやら・・・w

素数を求める~エラトステネスの篩~

No Comments

エラトステネスの篩(エラトステネスのふるい)は素数判定法の一種で、指定された整数以下の全ての素数を発見するための単純なアルゴリズムである。古代ギリシアの科学者、エラトステネスが考案したとされるため、この名がある。 ※Wikipediaより

Wikipediaさんを参考にエラトステネスの篩で素数を求めるプログラムを作ってみようと思います

まず手順 Wikipediaさんのそのままですが・・・w

1
整数を最初の素数である 2 から昇順で探索リストに羅列する。
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

2
リストの先頭の数を素数リストに記録する。
素数リスト:2
探索リスト:2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

3
前のステップで素数リストに加えられた数の全ての倍数を、探索リストから削除する。
素数リスト:2
探索リスト:3 5 7 9 11 13 15 17 19

4
探索リストの最大値が素数リストの最大値の平方よりも小さい場合、素数リストおよび探索リストに残っている数が素数となる。探索リストの最大値が素数リストの最大値の平方よりも大きい場合、ステップ 2 に戻る。
19 は 2 の平方よりも大きいので、ステップ 2 に戻る。
2
素数リスト:2 3
探索リスト:3 5 7 9 11 13 15 17 19
3
素数リスト:2 3
探索リスト:5 7 11 13 17 19
4
19 は 3 の平方よりも大きいので、ステップ 2 に戻る。
2
素数リスト:2 3 5
探索リスト:5 7 11 13 17 19
3
素数リスト:2 3 5
探索リスト:7 11 13 17 19
4
19 は 5 の平方よりも小さいので、リストに残っている数が素数である。
結果:2 から 20 までの数に含まれる素数は、
2 3 5 7 11 13 17 19

この手順の通りにJavaで書いてみた



import java.util.Iterator;
import java.util.LinkedList;
public class Eratosthenes {
	static LinkedList primes = new LinkedList(); //素数リスト
	static LinkedList numbers = new LinkedList(); //探索リスト
	static int N = 100000; //Nまでの素数を求める
	public static void main(String[] args) {
		//1.整数を最初の素数である 2 から昇順で探索リストに羅列する。
		for(int i = 2; i <= N; i++){
			numbers.add(i);
		}
		int prime;
		Iterator it;
		do{
			//2.リストの先頭の数を素数リストに記録する
			prime = numbers.getFirst();
			primes.add(prime);
			//3.前のステップで素数リストに加えられた数の全ての倍数を、探索リストから削除する
			it = numbers.iterator();
			while(it.hasNext()){
				if(it.next() % prime == 0)	it.remove();
			}
		//4.探索リストの最大値が素数リストの最大値の平方よりも大きい場合、ステップ 2 に戻る
		}while(numbers.getLast() > prime*prime);
		//4.探索リストの最大値が素数リストの最大値の平方よりも小さい場合、素数リストおよび探索リストに残っている数が素数となる
		it = numbers.iterator();
		while(it.hasNext()){
			primes.add(it.next());
		}
	}
}

本当に手順そのまま書けたw
もうちょっと改善の余地がありそうだけど、手順通りのほうが理解しやすいしよほど効率が求められない限りこれで十分かな
覚えとこー

Blue Taste Theme created by Jabox