▼解答編６
「息抜き：簡単な数値解析　〜エラトステネスのふるい〜」
　
← 前 　：　 次 →

問１の解答．
「１か，その数でしか割り切れない」が素数なので，その指定数までを １つずつ割り切れるかどうか判定していく手法を取ってみました． ただし多少は効率良くなるように，指定数の半分までを分母の対象にしています．

例えば指定数が「13」だった場合：
2 〜 6 までを対象にして，この中で割り切れる数があれば素数ではない．

問２の解答．
１つのプログラムで まとめてみました． 

「PrimeNumber.java」

public class PrimeNumber {
	/**
	 * @param args コマンド・ライン引数
	 * 
	 * メイン・メソッド．
	 */
	public static void main(String[] args) {
		PrimeNumber pn;
		int userNum;
		boolean[] isPrimeNumber;

		// 引数のエラー判定１（あるかないか）
		if(args.length!=1) {
			System.out.println("引数ないよ");
			System.exit(1);
		}

		// 引数のエラー判定２（自然数かどうか）
		try {
			userNum=Integer.parseInt(args[0]);
		} catch(NumberFormatException nfe) {
			userNum=-1;
		}
		if(userNum<0) {
			System.out.println("正の整数じゃないよ");
			System.exit(1);
		}

		// 自身のインスタンス生成
		pn=new PrimeNumber();
		// 結果保持用配列の確保
		isPrimeNumber=new boolean[userNum+1];

		// 指定数値分だけ繰り返し
		for(int i=0;i<isPrimeNumber.length;i++) {
			// 素数判定（独自仕様）
			isPrimeNumber[i]=pn.judgePrime(i);
		}
		// 結果の出力
		pn.outputResult(isPrimeNumber);

		System.out.println("");
		// エラトステネスのふるい
		isPrimeNumber=pn.hurui(userNum+1);
		// 結果の出力
		pn.outputResult(isPrimeNumber);
	}

	/**
	 * @param dstNum 判定する数値
	 * @return 素数であれば true
	 * 
	 * 対象数値が素数かどうか判定するメソッド．
	 */
	public boolean judgePrime(int dstNum) {
		int maxDstNum;

		// 0,1 は素数ではない
		if(dstNum<2) {
			return false;
		}

		// 判定する数値の半分までが計算対象
		maxDstNum=dstNum/2;
		for(int i=2;i<=maxDstNum;i++) {
			// 割り切れたら素数ではない
			if((dstNum%i)==0) {
				return false;
			}
		}

		return true;
	}

	/**
	 * @param dstNum 判定する最大値
	 * @return 素数であれば true を保持した配列
	 * 
	 * 対象数値以下全ての数値が素数かどうか判定するメソッド．
	 */
	public boolean[] hurui(int dstNum) {
		boolean[] isPrime;

		// 結果保持用配列の確保
		isPrime=new boolean[dstNum];
		// 初期化
		for(int i=2;i<isPrime.length;i++) {
			isPrime[i]=true;
		}
		// 0,1 は素数ではない
		isPrime[0]=isPrime[1]=false;

		// ふるい
		for(int i=0;i<isPrime.length;i++) {
			if(isPrime[i]) {
				// 求める素数より小さい全ての素数の倍数を除去
				for(int j=2*i;j<isPrime.length;j+=i) {
					isPrime[j]=false;
				}
			}
		}

		return isPrime;
	}

	/**
	 * @param isPrime 素数かどうかを保持した配列
	 * 
	 * 結果表示用メソッド．
	 */
	private void outputResult(boolean[] isPrime) {
		for(int i=0;i<isPrime.length;i++) {
			if(isPrime[i]) {
				System.out.print(i+",");
			}
		}
	}
}

　

補足：
もっと効率を高めるに「以下の条件にせよ」と，大悶より お叱りを受けました．

×：　指定数の x/2 までを〜
○：　指定数の √x までを〜

表紙へ戻る