エラトステネスの篩を実装した
恐らくプログラミング初学者が絶対に作るであろうプログラム - 野球のちエロ漫画時々まじめの続き
素数リストを得る有名なアルゴリズムであるエラトステネスの篩をJavaで実装してみました.
いい加減に作ったからエラトステネスの篩になっているか微妙だけど得られるリストは素数リストになっているようなのでまあ正常に動いているのでしょう.
意外とリスト生成に時間がかかるのですけど作り方の問題でしょうかね.
改良の余地ありかな
以下がコード
public class SieveOfEratosthenes { private LinkedList<Integer> primeNumList; private LinkedList<Integer> searchList; private int x; SieveOfEratosthenes(int x) { this.x = x; this.primeNumList = new LinkedList<Integer>(); this.searchList = this.storeSearchList(); } // 素数リストを得る public LinkedList<Integer> getPrimeNumList() { int tmpPrimeNumber; this.primeNumList.addLast(this.searchList.poll()); while (Math.pow(this.primeNumList.getLast(), 2) < this.searchList .getLast()) { tmpPrimeNumber = primeNumList.getLast(); this.primeNumList.addLast(this.searchList.poll()); for (int i = 1; i * tmpPrimeNumber <= this.searchList.getLast(); i++) { this.searchList.remove((Object) (i * tmpPrimeNumber)); } } for (int num : this.searchList) { this.primeNumList.add(num); } return this.primeNumList; } private LinkedList<Integer> storeSearchList() { LinkedList<Integer> searchList = new LinkedList<Integer>(); for (int i = 2; i < this.x; i++) { searchList.addLast(i); } return searchList; } }
エラトステネスの篩ってなんか型月作品とか厨二モノに出てくるキーアイテムみたいな名前だよなあ…