RSS

素数の計算

19 11月

「エラトステネスのふるい」で素数計算を行う。

 

Main.java

import java.math.*;
import java.util.*;
// エラトステネスのふるい Sieve of Eratosthenes
public class Main {

 // メインプログラム
 public static void main(String[] args) {
  System.out.println("Prime Numbers by Sieve of Eratosthenes\n");

  // コマンドライン引数があれば素数を求める範囲として使う。
  int mx = 1000;  // 素数を求める範囲のデフォルト値を1000とする。
  if (args.length != 0) {
   try
   {
    mx = Integer.parseInt(args[0]);
   }
   catch (Exception e) {

   }
  }

  // 計算する。
  ArrayList<PrimeNumber> primes = Eratosthenes(mx);

  // 結果を表示する
  for (PrimeNumber n : primes) {
   if (n.isPrime) {
    System.out.println(n.number);
   }
  }
 }

 // 素数計算
 public static ArrayList<PrimeNumber> Eratosthenes(int mx) {
  // 素数候補の一覧
  ArrayList<PrimeNumber> primes = new ArrayList<PrimeNumber>();
  int first = 1; // 素数候補の位置

  // 2を素数として登録しておく
  primes.add(new PrimeNumber(2, true));
  // 素数候補を羅列する (偶数は除く)
  for (int i = 3; i <= mx; i += 2) {
   primes.add(new PrimeNumber(i, true));
  }

  // 次の素数候補が存在するかどうか
  boolean noc = true;
  // 素数候補が存在する間繰り返す。
  while (noc) {
   // 素数候補の先頭の数を素数とする。
   primes.get(first).isPrime = true;
   int n = primes.get(first).number;

   // 先頭の数の倍数を素数候補から外す。
   for (PrimeNumber p : primes) {
    if (p.number % n == 0 && p.number > n) {
     p.isPrime = false;
    }
   }

   // 次の素数候補の位置を決定する。
   int i = first + 1;
   int n0 = primes.get(i).number;
   if (n0 * n0 >= mx) {
    break;
   }
   while (n0 * n0 < mx) {
    if (primes.get(i).isPrime) {
     first = i;
     noc = true;
     break;
    }

    noc = false;
    i++;
    n0 = primes.get(i).number;
   }
  }

  return primes;
 }
}

PrimeNumber.java

public class PrimeNumber {
 public int number;
 public boolean isPrime;

 public PrimeNumber(int n, boolean f) {
  number = n;
  isPrime = f;
 }
}

コンパイルと実行
$ java Main.java PrimeNumber.java
$ jar cfm prime.jar manifest.mf *.class
$ java -jar prime.jar 1000

manifest.mfの内容

 Main-Class: Main

 
コメントする

投稿者: : 2010/11/19 投稿先 Java

 

タグ: , , ,

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中