X
頭いい人来て：　Nが素数かどうかを調べるには
■ このスレッドは過去ログ倉庫に格納されています
0001以下、5ちゃんねるからVIPがお送りします
垢版 |
2022/07/25(月) 10:25:18.653ID:XpI4m9sy0
２からN-1までで割ってみてあまりがゼロになることがあれば非素数
一回もなければ素数

２から調べ始めてN-1まで調べなくてもN/2位まででも大丈夫そうな気がするんだけど
どこまで調べれば良いかってどうやって考えればいいの？
0002以下、5ちゃんねるからVIPがお送りします
垢版 |
2022/07/25(月) 10:26:16.404ID:MUQg4Q6m0
恥ずかしいなら俺がＮに直接聞いてやるよ
0003以下、5ちゃんねるからVIPがお送りします
垢版 |
2022/07/25(月) 10:27:00.622ID:Ozs3a+bV0
二進数の最後の一桁
0004以下、5ちゃんねるからVIPがお送りします
垢版 |
2022/07/25(月) 10:28:05.507ID:Flee9cYZ0
Nが素数ではない場合N=a×bと表せるから
Nの平方根まで調べれば良い
0005以下、5ちゃんねるからVIPがお送りします
垢版 |
2022/07/25(月) 10:28:19.754ID:/i7Lo4QY0
N/2までだよ
割れる最小の整数が2だから
0006以下、5ちゃんねるからVIPがお送りします
垢版 |
2022/07/25(月) 10:28:51.914ID:/i7Lo4QY0
>>4
言われるとこれが正しかった気がする
0007以下、5ちゃんねるからVIPがお送りします
垢版 |
2022/07/25(月) 10:30:08.727ID:hj0p+WXI0
天才理系ぼく「検索サイトに入力する｣
0008以下、5ちゃんねるからVIPがお送りします
垢版 |
2022/07/25(月) 10:31:22.294ID:XpI4m9sy0
>>4
あーなるほど
天才だな

面積でイメージすると
平方根まで調べたらそれより後は今まで調べたものと同じだな
0009以下、5ちゃんねるからVIPがお送りします
垢版 |
2022/07/25(月) 10:31:24.684ID:nkz+zJ3+M
Nくんは素数って言ってたよ
0010以下、5ちゃんねるからVIPがお送りします
垢版 |
2022/07/25(月) 10:35:00.922ID:Flee9cYZ0
>>6
俺も自信ない
0011以下、5ちゃんねるからVIPがお送りします
垢版 |
2022/07/25(月) 10:36:27.016ID:IfdilQr8M
夏厨のプログラミングの課題か
0012以下、5ちゃんねるからVIPがお送りします
垢版 |
2022/07/25(月) 10:38:10.923ID:t3PytNqu0
エラトステネス……
なんでもない
0013以下、5ちゃんねるからVIPがお送りします
垢版 |
2022/07/25(月) 10:39:02.412ID:ypphJETVp
鈴木貫太郎が詳しく説明してる
0014以下、5ちゃんねるからVIPがお送りします
垢版 |
2022/07/25(月) 10:39:48.446ID:0tw1yekd0
√nまででいい
0015以下、5ちゃんねるからVIPがお送りします
垢版 |
2022/07/25(月) 10:40:04.379ID:eQZiAekH0
割ってみる数って2以外は奇数だけでよくね？
0016以下、5ちゃんねるからVIPがお送りします
垢版 |
2022/07/25(月) 10:41:02.447ID:Flee9cYZ0
N=a×bでaが√Nより大きい時
bが√Nより小さくなるってどうして分かる？🤔
0017以下、5ちゃんねるからVIPがお送りします
垢版 |
2022/07/25(月) 10:42:30.046ID:YiAdRrEfa
プログラム作れ
0018以下、5ちゃんねるからVIPがお送りします
垢版 |
2022/07/25(月) 10:47:33.871ID:h5xBkm1Ua
エラトステネスのふるいね
0020以下、5ちゃんねるからVIPがお送りします
垢版 |
2022/07/25(月) 10:50:56.325ID:o1/GGfR90
>>16
N/√N=√N

a > √N
の時、

N/a=b<√N
0021以下、5ちゃんねるからVIPがお送りします
垢版 |
2022/07/25(月) 10:53:06.332ID:Flee9cYZ0
>>20
うおおおお
0022以下、5ちゃんねるからVIPがお送りします
垢版 |
2022/07/25(月) 10:58:47.934ID:XpI4m9sy0
>>16
N=axbだから
a=√Nの時に
b=√Nじゃん

直観的に
aがその状態から増えたらbは小さくなるしかない気がする

それって√Nより小さくなるってことだよね
0023以下、5ちゃんねるからVIPがお送りします
垢版 |
2022/07/25(月) 11:01:34.600ID:XpI4m9sy0
>>15
そうだね
3以外3の倍数も要らないし。。。
5以外5の倍数も要らない

みたいなことを考えると2だけ特別視するのもあれだな
プログラムなら少しでも計算量減らすために２や３，5の倍数は予め弾いちゃってもいいのかも
0024以下、5ちゃんねるからVIPがお送りします
垢版 |
2022/07/25(月) 11:05:28.277ID:eQZiAekH0
>>23
倍数かどうか判断するのがまたコストかかるじゃん
2だけならカウントアップする数変えるだけでok
0025以下、5ちゃんねるからVIPがお送りします
垢版 |
2022/07/25(月) 11:18:25.691ID:ZdXllg5B0
2<N<100くらいまでなら余裕だけど100万とかは数学者も頑張ってるレベルだから無理
0027以下、5ちゃんねるからVIPがお送りします
垢版 |
2022/07/25(月) 11:56:18.523ID:iX2FqlPPM
ルートとった数までみればいい
■ このスレッドは過去ログ倉庫に格納されています
ニューススポーツなんでも実況