2016.02.01
数学
素数判定
素数とは、1と自分自身でだけで割り切れる2以上の数です。(1は素数ではありません)
2、3、5、7、11、13、17、19、23 …
判定する例として素数である11で説明します。この場合√11の整数部は3です。2から3の値で11を割っていき、割り切れなければ素数としています。ここで、なぜ3(=√Nの整数部)より大きい整数で割る必要がないかを考えます。11を4で割った商は2で余り3です。11を5で割った商は2で余り1です。11を6で割った商は1で余り5です。このように商が3より大きい値になりません。よって、仮に4と5で割り切れるなら、2か3でも割り切れていたはずです。よって、√Nを割る数の上限にしています。
判定時間を短くするために上限を√Nとしていますが、整数Nを2からN-1までの値で素数判定を行ってもよいです。判定結果は同じですが、判定時間が長くなります。
Javaソースコード
PrimeNumber1.java
001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030 031 032 033 034 035 036 037 038 039 040 041 042 043 044 045 046 047 048 049 050 051 052 053
public class PrimeNumber1 { // 素数判定メソッド private static boolean isPrimeNumber( int num ) { // 1以下は素数ではない if ( 1 >= num ) return false; // 2の場合は素数 if ( 2 == num ) return true; // 素数判定 int n = (int)Math.sqrt( num ); for ( int i = 2; i <= n; ++ i ) { // 余り0で割り切れるかを判定 if ( 0 == ( num % i ) ) return false; } // numが2~nで割り切れなかったので素数 return true; } // メイン public static void main( String[] args ) { // 変数の宣言 int number; // 素数かどうか調べる整数値 // 入力した引数が1つ以上かを調べる if ( 1 > args.length ) { // 入力した引数が1つ未満の場合、使用方法を表示する System.out.println( "PrimeNumber1 [整数値]" ); return; } // 引数をint型に変換しnumberに代入 try { number = Integer.parseInt( args[ 0 ] ); } catch( NumberFormatException ne ) { // args[0]が数字ではない System.out.println( "[整数値]の取得に失敗しました" ); return; } // 素数かどうか調べる if ( true == isPrimeNumber( number ) ) System.out.println( number + "は素数です" ); else System.out.println( number + "は素数ではない" ); } }
コンパイル ソースコードが「ANSI」の場合
C:\talavax\javasample>javac -encoding sjis PrimeNumber1.java
コンパイル ソースコードが「UTF-8」の場合
C:\talavax\javasample>javac PrimeNumber1.java
実行
C:\talavax\javasample>java PrimeNumber1 5
1つ目の引数に5を渡して、5が素数かどうか調べます。
出力結果
5は素数です
素数はどうかを判定するisPrimeNumberメソッドの説明をします。
003
private static boolean isPrimeNumber( int num )
005 006
// 1以下は素数ではない
if ( 1 >= num ) return false;
numが1以下の場合、素数ではないのでfalseを返しています。
008 009
// 2の場合は素数
if ( 2 == num ) return true;
numが2の場合、素数なのでtrueを返しています。
011 012 013 014 015 016
// 素数判定 int n = (int)Math.sqrt( num ); for ( int i = 2; i <= n; ++ i ) { // 余り0で割り切れるかを判定 if ( 0 == ( num % i ) ) return false; }
018 019
// numが2~nで割り切れなかったので素数 return true;
以上です。
関連コンテンツ
割り算で「割り切れる」、「割り切れない」ってどういうこと?