[過去ﾛｸﾞ] 高校数学の質問スレ Part410 (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
403: [sage] 2021/03/02(火) 14:25:19.93 ID:IddjJv3w(6/7) AAS
まぁ人格異常者だわな
404(1): [sage] 2021/03/02(火) 14:34:34.19 ID:KDDWDoqg(8/9) AAS
>>377
１０００を超える合成数も計算させているから、計算量は多いよ。
outerを使ったコードも読めないのに
>378みたいに、もちろん変わらんというアホもいるが。
でも１００００程度なら１秒もかからず答が返ってくる。
やってみたら、0.6秒で10000までの素数をリストアップ。
> system.time((1:10000)[-outer(2:10000,2:10000)][-1])
user system elapsed
0.60 0.03 0.66
まあ、省スペースな分だけ計算量が多くてCPUに負荷はかかっていると思う。
10万にするとエラーがでた。
Error: cannot allocate vector of size 74.5 Gb
405: [sage] 2021/03/02(火) 15:38:10.14 ID:s/RK2FsU(1) AAS
>>399
スルーが一番は永遠の真理
406(3): [sage] 2021/03/02(火) 17:53:50.21 ID:KDDWDoqg(9/9) AAS
「pが素数ならp^4+14は素数ではないことを示せ」
という京大の問題だけどなんで5ではなくて14に問題設定したのだろう？
p^2+5でもいい気がするし。
407(3): [sage] 2021/03/02(火) 19:12:47.60 ID:K/oD/Qs/(1) AAS
pが奇数のとき偶数でアウト。p=2 のとき 9 でアウト。
それぢゃあ中学校の問題だろ。
408(1): [sage] 2021/03/02(火) 20:34:33.60 ID:lj5Vcry7(1) AAS
>>407
2より大きい素数は奇数で、奇数の四乗が偶数にはならんでしょ。
409: [sage] 2021/03/02(火) 21:42:45.70 ID:Sn8MQdP2(1) AAS
ガイジ現る
410: [sage] 2021/03/02(火) 22:04:06.93 ID:IddjJv3w(7/7) AAS
よく>>406のレベルで数学板に書き込む気になるよな
411(3): イナ ◆/7jUdUKiSM [sage] 2021/03/02(火) 23:35:23.06 ID:+1/2s3pW(1) AAS
前>>208
>>385
楕円型ステーキを圧縮して、
半径10の円型を2:1に分ける切断面の長さを考えると、
2θ-2sinθcosθ=2π/3
2θ-sin2θ=2π/3
20sinθ=16.66
θ=56.4068°
16.66ぐらいなんだけど、
妙に数字が並ぶところを見ると50/3なのかな？
412: [sage] 2021/03/03(水) 00:01:22.25 ID:9ZpkypMa(1) AAS
>>408
え？
413(1): [] 2021/03/03(水) 00:36:08.51 ID:hMNi8ANp(1/3) AAS
>>404
>計算量は多いよ。
O(n^2)は多すぎだね。
ふつうに割り算を繰り返して素数判定する方法でもO(n^1.5)だから
その方法より勝っている。エラトステネスの篩だと0(nloglogn)で
もっと少ない。
プログラムは一行で済むかもしれないけど計算量が多すぎて駄目です。
414(1): [] 2021/03/03(水) 00:37:23.22 ID:hMNi8ANp(2/3) AAS
×エラトステネスの篩だと0(nloglogn)
○エラトステネスの篩だとO(nloglogn)
目が悪くてスマン
415: [sage] 2021/03/03(水) 00:54:35.93 ID:CGS3YUU8(1) AAS
エラトステネスの篩はdpの演習でかなり出てくるテーマなんだけどな
まぁ完全我流の俺様プログラマーもどきには何いうても通じんわな
416: [sage] 2021/03/03(水) 00:56:53.53 ID:wf1J4znc(1) AAS
与えられた n 以下の素数リストの作成法
エラトステネス：（要するメモリサイズは、n 程度）
1〜n までのリストを作成し、1を消す。
2に印をつけて、(2より大きい)2の倍数をリストから消す。
印を次の数字(=3)に移動し、(その数字より大きい)その数の倍数をリストから消す。
以下同様のことを√nまで行う。
某異人：（要するメモリサイズは、n^2 程度）
1〜n までのリストを作成する。
(2〜n)×(2〜n)のかけ算の表を作成する。
リストから、表に載っている数字と1を消す。
多くの人が思ってる某異人版改善案
・(2〜n)×(2〜n)のかけ算の表を作成するから、メモリが足りなくなる。
→せいぜい、(2〜√n)×(2〜n)で十分。
・というか、表の値を保存しておく必要が全く無い。
→2≦i≦√n,2≦j≦n/iのループの中で、i*jがリスト内にあったら消せばいい。
・iが4以上で2の倍数の時とか、iが6以上で3の倍数の時って、無駄なループしてるよね
→この無駄を省くためには．．．あれ、その工夫の先にあるのって、エラトステネスの簁そのものじゃね
417: [] 2021/03/03(水) 01:07:37.86 ID:hMNi8ANp(3/3) AAS
もともとの問題は1000以下の素数が何個あるか上限を見積もる
問題なので、ちと違う方向に進んでいるのでは？
素数の重複しない倍数の個数を見積もれればいいわけで、素数
を求めたいわけではない。
418: [sage] 2021/03/03(水) 04:49:19.48 ID:HkpiSwix(1/2) AAS
>>413-414
何だ nloglogn って?
それ n(log_e(log_e(n))) って意味？
だとすると n(log_e^e(n)) って事？
419: [sage] 2021/03/03(水) 07:05:23.60 ID:BYgBOF1p(1) AAS
なんでやねん
420(1): [sage] 2021/03/03(水) 09:18:48.99 ID:bYsQl+7T(1/3) AAS
>>407
なんで9がアウトなんだ？
421: [sage] 2021/03/03(水) 09:27:57.68 ID:J9rwAVza(1) AAS
9は素数じゃないだろ
422: [sage] 2021/03/03(水) 09:37:45.85 ID:fLSs1mYb(1/3) AAS
とんでもないアホなのか？
上下前次1-新書関写板覧索設栞歴
あと 580 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.013s