Java 素数をすべて表示する

Question

http://kitako.tokyo/lib/JavaExercise.aspx?id=106
こちらのサイトを利用しています

練習問題 6 - 7
ある数が素数かどうかを判定するメソッドを作成しなさい。
このメソッドを使用して 10000 以上 10100 未満の素数をすべて表示するプログラムを作成しなさい。

回答

public static void main( String[] args )
{
    for( int n = 10000 ; n < 10100 ; n++ )
        if( IsPrimeNumber( n ) )
            System.out.print( n + " " );
}

static boolean IsPrimeNumber( int num )
{
    if( num <= 3 )
        return true;

    for( int i = 2 ; i <= ( num / 2 ) ; i++ )
        if( ( num % i) == 0 )
            return false;

    return true;
}

メソッドの中で回しているfor文の条件式（真ん中のところ）について質問したいです。

iがnumと同じになってしまうとfalseが返されてしまうので
その手前でfor文が終わるようにする必要があると解釈しました。
その場合

    for( int i = 2 ; i < ( num - 2 ) ; i++ )
        if( ( num % i) == 0 )
            return false;

まで回す方が間違いなさそうだと思ってしまいます･･･
素数自体どんどん減っていくのでnumの半分くらいまでCHKしたら
絶対素数！と言い切れたりするのでしょうか

Answer 1

半分ではなく、平方根まで検索すれば言い切れますよ。
引数がint型だけら平方根+1でいいはずです。

Comments

[nyoi]

言い切れますね
平方根の存在を全く忘れていました
はるか昔におこなったなぁ･･･遠い目
α≤√N　ありがとうございました

[stdio]

私も教えてもらうまで、素数が平方根まで調べれば言い切れるなんて発想すらしませんでした^^;

[nyoi]

ええ　平方根を使う日が来るなんてもうもう･･･
でも過去の勉強を利用できるなんてちょっとうれしいです♪

Answer 2

素数自体どんどん減っていくのでnumの半分くらいまでCHKしたら

絶対素数！と言い切れたりするのでしょうか

例えば42を2数の積として表現すると、次のように列挙できます。

 1 x 42
 2 x 21
 3 x 14
 6 x  7
 7 x  6
14 x  3
21 x  2
42 x  1

このように除数が途中で折り返すので、半分だけチェックすれば良いことが分かります。
ただし『真ん中の数』は　n/2 ではなく √n なので、条件は <= Math.sqrt(num) で充分です。

i <= num / 2 は誤り？

• f(x) := x/2 も g(x) := √x も単調増加する関数である
• x = 0, 4 のとき f(x) = g(x) である
• f'(x) = 1/2, g'(x) = 1/(2√x) より、 x >= 1 のとき f'(x) >= g'(x)

よって x >= 4 ならば f(x) >= g(x) である。

IsPrimeNumberは引数numの値が3以下のときは早期にtrueを返してるので、
ループの条件として i <= num / 2 を用いても問題は無いです。非効率的なだけで。

---

論理に穴がある気がしてしょうがない。数学難しい。

Comments

[nyoi]

ありがとうございます！
非効率だけど　間違いではない　
大変よくわかりました

100-200の繰り返しだと問題ない場合でも
素晴らしく多い回数繰り返す場合には
必要のないものをしっかり省く必要があるのですね

そもそも平方根なら半分もいらないわ･･･と感じるまで成長できました
おそらくMath.sqrt()のコードはまだ習ってないねハート
という段階の設問だったのだろうと受け入れる感じにしてみました

ありがとうございました～

[swordone]

x>0に限れば、x/2≧√x と(x/2)^2≧(√x)^2は同値。
x^2≧4x
x>0より両辺をxで割ると、
x≧4
よってx≧4の時x/2≧√x

Answer 3

ある数 x が**素数ではない（合成数）**とき、x = A × B の形で表すことができます。
A, B のうち小さい方を n とすると、n が最大の値になるのは、A = B のときです。
ということはこの数は x = n * n ですから、 nの自乗で表せることになります。

よって、約数としては最大でも sqrt(x) までで割り切れるかどうか判定すればよいことになります。
※より大きい数値で割り切れた場合（X/B = A）となるので、既に判定済みの A が商として出てきます

ですのでループの最大は sqrt(x) でよいのです。

ついでに言えば約数が合成数の場合は考慮する必要がない（A × B の A が より小さい数の組 a×b で表せるなら、そもそもaで割り切れている判定ができているので）ので、割る数の候補は素数を並べておけばよいことになります。

Comments

[nyoi]

ありがとうございます！
候補の素数を並べればいいんじゃない？までは心が動いたのですが
それをどうやって書けばいいのかがわからなかった様子です
素因数分解って昔やったな　って思いだしました
過去の勉強を利用するシーンがあって驚きでした･･･

ありがとうございました～

Answer 4

numの半分くらいまでCHKしたら絶対素数！と言い切れたりする

素数判定は、sqrt(N)+αまででOKです。

Comments

[nyoi]

平方根を出すｺｰﾄﾞを教えてくださってありがとうございます
double型ですね
注意して使いたいです　ありがとうございました～

Answer 5

ある数の約数の集合は 1 と自分自身を含みます。
約数がこの 2 つしかないときが素数です。
では、1 と 自分自身以外の約数はだいたいどんな数になるでしょか？

x が素数でない場合, x = p * q と 2 つの数で表わせたとします。(p != 1, q != 1とする)
p が大きくなれば、q は小さくなります。
p と q が逆転する境い目は p = q です。その場合の p, q の値は x の平方根です。

つまり、p を 2, 3, ... x の平方根 と増やしながらしらべていって割り切れるものがみつからなかったら、調べるのを中止してよいことになります。
(もし x の平方根 より大きい数でわりきれたなら、その商は x の平方根より小さいです。
だったら、p を 2 ,3 .. と調べていた途中で その商の値でわりきれていたことを発見できたていたはず。)

Comments

[nyoi]

ありがとうございます
平方根ですね　その単語を使う時が来て驚いておりました
ｐ*ｐの概念～　記憶の引き出しがやっとでてまいりました
丁寧に書いていただいてありがとうございました！