2016/02/01 公開
・素数判定
素数とは1と自分自身でだけで割り切れる2以上の数です。(1は素数ではありません)
ここで説明する方法は、判定する整数Nを2から順番に√Nまでの数で割っていき、割り切れたら素数ではない、割り切れなかったたら素数と判定するものです。
以下が、素数判定のJavaソースコードです。
PrimeNumber1.java ← クリックしてダウンロードページに移動001: public class PrimeNumber1 { 002: // 素数判定メソッド 003: private static boolean isPrimeNumber( int num ) 004: { 005: // 1以下は素数ではない 006: if ( 1 >= num ) return false; 007: 008: // 2の場合は素数 009: if ( 2 == num ) return true; 010: 011: // 素数判定 012: int n = (int)Math.sqrt( num ); 013: for ( int i = 2; i <= n; ++ i ) { 014: // 余り0で割り切れるかを判定 015: if ( 0 == ( num % i ) ) return false; 016: } 017: 018: // numが2~nで割り切れなかったので素数 019: return true; 020: } 021: 022: 023: // メイン 024: public static void main( String[] args ) { 025: // 変数の宣言 026: int number; // 素数かどうか調べる整数値 027: 028: // 入力した引数が1つ以上かを調べる 029: if ( 1 > args.length ) { 030: // 入力した引数が1つ未満の場合、使用方法を表示する 031: System.out.println( "PrimeNumber1 [整数値]" ); 032: return; 033: } 034: 035: 036: // 引数をint型に変換しnumberに代入 037: try { 038: number = Integer.parseInt( args[ 0 ] ); 039: } 040: catch( NumberFormatException ne ) 041: { 042: // args[0]が数字ではない 043: System.out.println( "[整数値]の取得に失敗しました" ); 044: return; 045: } 046: 047: // 素数かどうか調べる 048: if ( true == isPrimeNumber( number ) ) 049: System.out.println( number + "は素数です" ); 050: else 051: System.out.println( number + "は素数ではない" ); 052: } 053: }
PrimeNumber1を実行
C:\talavax\javasample>java PrimeNumber1 5
1つ目の引数に5を渡して、素数かどうか調べます。
実行結果
5は素数です
素数はどうかを判定するisPrimeNumberメソッドの説明をします。
003: private static boolean isPrimeNumber( int num )
int型の変数numが素数であればtrue、素数でなければfalseを返すisPrimeNumberメソッドを作成しています。
005: // 1以下は素数ではない 006: if ( 1 >= num ) return false;
numが1以下の場合、素数ではないのでfalseを返しています。
008: // 2の場合は素数 009: if ( 2 == num ) return true;
numが2の場合、素数なのでtrueを返しています。
011: // 素数判定 012: int n = (int)Math.sqrt( num ); 013: for ( int i = 2; i <= n; ++ i ) { 014: // 余り0で割り切れるかを判定 015: if ( 0 == ( num % i ) ) return false; 016: }
numを2~nまでの整数で順番に割っていき、割り切れたら素数ではないのでfalseを返しています。ここで、n=(int)√numはnumの平方根の小数点以下を切り捨てた整数値です。割り切れるかの判定をnで打ち切れる理由は、numをnより大きい数値で割った商はn以下になり、nより大きい数値で割り切れるなら、n以下の商で既に割り切れているためです。(分かりづらかったらゴメンなさい)
例として11の素数で説明します。この場合n=(int)√11=3です。このソースコードに当てはめるとi=2~3の値で11を割っていき、割り切れなければ素数としています。ここで、なぜ3より大きい整数で割る必要がないかを考えます。11を4で割った商は2で余り3です。11を5で割った商は2で余り1です。11を6で割った商は1で余り5です。このように商が3より大きい値になりません。よって、仮に4と5で割り切れるなら、2か3でも割り切れていたはずです。
こんな感じです。
018: // numが2~nで割り切れなかったので素数 019: return true;
numを2~nまでの整数で順番に割っていき、割り切れなかったら素数なのでtrueを返しています。
■他の素数の求め方
素数リスト作成 | 素数リストの作成方法を解説 |
■関連コンテンツ
平方根 | Math.sqrtの使い方について解説 |
![]() |
剰余(余り)計算剰余(余り)をを計算するプログラムの紹介と、その結果を表示する方法を解説 |
![]() |
for文繰り返し処理に使用するfor文をJavaのソースコードを使って説明しています。 |
![]() |
計算結果の表示足し算(加法)/引き算(減法)/掛け算(乗法)/割り算(除法)の使い方を説明 |
■新着情報
2021.12.21 | 現在の日時を取得 | いまの年月日、時分秒? |
■広告
