ton-up blog – とんぶろ

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

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

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

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

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