2016.02.01
2025.03.17
数学
素数判定
素数とは、１と自分自身でだけで割り切れる２以上の数です。（１は素数ではありません）
2、3、5、7、11、13、17、19、23 …
判定する例として素数である１１で説明します。この場合√１１の整数部は３です。２から３の値で１１を割っていき、割り切れなければ素数としています。ここで、なぜ３（＝√Nの整数部）より大きい整数で割る必要がないかを考えます。１１を４で割った商は２で余り３です。１１を５で割った商は２で余り１です。１１を６で割った商は１で余り５です。このように商が３より大きい値になりません。よって、仮に４と５で割り切れるなら、２か３でも割り切れていたはずです。よって、√Nを割る数の上限にしています。
判定時間を短くするために上限を√Nとしていますが、整数Nを２から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; // 素数かどうか調べる整数値 // 入力した引数が１つ以上かを調べる if ( 1 > args.length ) { // 入力した引数が１つ未満の場合、使用方法を表示する 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
１つ目の引数に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;
以上です。
素数に関するコンテンツ
「素数」に関係があるコンテンツをまとめています。
関連コンテンツ
広告
