なんJ民ってパソコン大先生だし、プログラミングで『エラトステネスの篩』ぐらい書けるよな?

0001 名無しさん 2024/01/09(火) 11:01:18.51 ID:5WYyf8cB0

哲学者の東浩紀さんと思想史と近代科学史(特にコンピュータ史)の本を一緒に書いてみようという企画が今年から立ち上がった。

すると東さんがある日の生放送で、「しかし俺も最低限プログラムくらいかける必要があるんじゃないか。しかし最低限のプログラムとは何か」と言っていたところ、シラスの桂さんが「エラトステネスの篩ふるいとかですかねえ」と言っていて、もうエラトステネスと聞いたら黙ってはいられない吾輩が怒涛の勢いで生放送したところ、東さんが一番乗りで入ってきてくれたのでその場でライブコーディングしながらプログラムの書き方を簡単に教えることにした。

http://kenmo.chinpo

0002 名無しさん 2024/01/09(火) 11:02:47.76 ID:SBQBmAGJ0

ああ、あれね…まあやれるね…

0003 名無しさん 2024/01/09(火) 11:02:48.78 ID:cMxg7ZGi0

昔はよくエクストラテス？の櫛で遊んだもんよ

0004 名無しさん 2024/01/09(火) 11:03:12.08 ID:xA9V5TCB0

マイコンボードでオリジナルデバイスなら作ったことある

0005 名無しさん 2024/01/09(火) 11:03:30.57 ID:YzRVQ0IH0

鰤がなんだって？

0006 名無しさん 2024/01/09(火) 11:04:46.43 ID:5+roMhCC0

ネオエクスデス

0007 名無しさん 2024/01/09(火) 11:04:49.61 ID:0cBP5YIO0

今は哲学者なんて肩書きになってんのか

0009 名無しさん 2024/01/09(火) 11:06:29.93 ID:oVGZSPv0x

AI使って書けば？

0010 名無しさん 2024/01/09(火) 11:06:42.39 ID:nzlbQTEA0

とんでもねぇ鰤だよ

0011 名無しさん 2024/01/09(火) 11:06:42.92 ID:yHEVM2Ys0

チャットGPTに頼んで

0012 名無しさん 2024/01/09(火) 11:07:28.43 ID:nnSHDjkY0

エラトステネス節って歌があるの？

0013 名無しさん 2024/01/09(火) 11:07:38.50 ID:8m3YGgiQM

再帰か
ツリービューを使うアプリだと多用するね

0014 名無しさん 2024/01/09(火) 11:07:44.53 ID:feibhCvIa

printf(“エラトステネスの篩”);

0015 名無しさん 2024/01/09(火) 11:08:27.24 ID:akqPQ7kQ0

むかし綺麗だからマンブロ描画してた

0016 名無しさん 2024/01/09(火) 11:09:24.24 ID:4Ja/dlXa0

まずはレコード長の設計からやらないとな

0017 名無しさん 2024/01/09(火) 11:09:32.71 ID:RYczQSMD0

あの節だろ？余裕

0018 名無しさん 2024/01/09(火) 11:10:49.40 ID:fYbGZAZOM

10 print “ｴﾗﾄｽﾃﾈｽﾉﾌﾙｲ”:beep:goto 10

0020 名無しさん 2024/01/09(火) 11:10:51.05 ID:nnSHDjkY0

♪はぁ～2,3,5,7,11,13

0021 名無しさん 2024/01/09(火) 11:11:00.56 ID:1/oVIQef0

超デカい数の素数探索ってどんなアルゴリズムでやってんの？
エラトステネスの篩だと先にメモリ確保しないといけないから向いてないよね？

0024 名無しさん 2024/01/09(火) 11:11:47.29 ID:kUq9ArLu0

>>21
それひみつや。銀行の暗号と関係あるでの。

0039 名無しさん 2024/01/09(火) 11:20:35.50 ID:E+eC6R8V0

>>21
大きな n について 2ⁿ – 1 が素数かどうか確認する

0022 名無しさん 2024/01/09(火) 11:11:06.76 ID:kUq9ArLu0

素数出すやつなら書いたで。それで

１億までは、素数全部出してみて、ファイルに保存してある。

ＢＡＳＩＣで書いたんだが
アセンブリ言語でも書いてみた。
動いたけど、数値を数字のＡＳＣＩＩコードに変換するのは放置している。

0076 名無しさん 2024/01/09(火) 11:50:07.15 ID:akqPQ7kQ0

>>22
コテハン変えたんや

0023 名無しさん 2024/01/09(火) 11:11:20.40 ID:nV9MPk6Rd

ChatGPTかbingに頼める
もう正常系プログラミングは人間がやる必要ない

0025 名無しさん 2024/01/09(火) 11:13:01.35 ID:3loOyQoK0

古代ギリシャの言葉が入るとなんかムダに深遠っぽい印象が出るな

0026 名無しさん 2024/01/09(火) 11:13:33.72 ID:ZcBSq4ZV0

自然数n受け取って
nまでのリスト作って全部Trueで初期化して
√nまでループして
あとなんだっけ忘れた

0027 名無しさん 2024/01/09(火) 11:13:36.12 ID:kUq9ArLu0

確か、Ｃでも書いてみた。たぶん、やればJavaでも書ける。

0028 名無しさん 2024/01/09(火) 11:14:01.23 ID:w1u1bfWW0

そうっすね

0029 名無しさん 2024/01/09(火) 11:14:48.51 ID:kUq9ArLu0

ふふふ

ぼく、元一級現二級統合失調症でナマポで、フードデリバリー屋さんやねん。東大理一中退や。

0030 名無しさん 2024/01/09(火) 11:15:37.17 ID:VF/J0j200

単純に割って素数かどうか判定するやつだろ
時間かければなんとかなりそう

0033 名無しさん 2024/01/09(火) 11:17:08.90 ID:kUq9ArLu0

>>30
あんな

６ｎ±１、だけ調べればいいのはわかるよな。

0031 名無しさん 2024/01/09(火) 11:16:23.96 ID:FEWw5HqS0

大先生な

0035 名無しさん 2024/01/09(火) 11:18:27.95 ID:a5bn5bQTa

「素数を小さい順にn個求めて」ってエラトステネスの篩できれいに書ける？
n個に足りなかったらもっかいでかいサイズでやらなきゃダメ？

0036 名無しさん 2024/01/09(火) 11:18:45.68 ID:4QrJmYrD0

ヒポクラテスの誓いね書けるよ

0040 名無しさん 2024/01/09(火) 11:21:10.79 ID:kUq9ArLu0

でだな、最大どのくらいの数値、例えば、一億まで調べてくれ、と。そすっと、１億の√、１万までの、素数を、倍にしていけばいいんだってさ。これをだね

デキルやつは、回帰に、書けるそうなのだがをれはポンコツなので
奇数全部調べたんじゃなかったかな。

0041 名無しさん 2024/01/09(火) 11:24:40.10 ID:kUq9ArLu0

わかるよな？√、√の繰り返しすればさ。

２，３，５，７，１１のレベルの

“種”、まで、さかのぼれるのよ。

0045 名無しさん 2024/01/09(火) 11:26:45.15 ID:kUq9ArLu0

>>41
たとえば、ここまでわかってたなら、１２１までの、素数は、割り出せるのな。そしたなら、次は、１２１✕１２１までは、割り出せる、その繰り返しで、あとは回帰。

0042 名無しさん 2024/01/09(火) 11:25:00.68 ID:nWmDPiVd0

奥歯ガタガタ言わせ節

0043 名無しさん 2024/01/09(火) 11:25:49.45 ID:f0VdJfek0

クラスの継承だろ

0044 名無しさん 2024/01/09(火) 11:25:54.03 ID:GEVeRxFyr

再帰みたいに不必要な判定をなくしたいってこと？
言葉は知らなくても中級位のプログラマなら普通にやってんじゃね？

0046 名無しさん 2024/01/09(火) 11:27:18.17 ID:kUq9ArLu0

>>44
大先生丸出しだなおまえｗｗｗｗ

0047 名無しさん 2024/01/09(火) 11:29:06.11 ID:kUq9ArLu0

√、まで調べればいい、っつーことは、先人の、賢者が、発見したことなのね。

0049 名無しさん 2024/01/09(火) 11:29:53.45 ID:ITBcqvaN0

ヒルナンデスを見た！

0051 名無しさん 2024/01/09(火) 11:30:03.06 ID:kUq9ArLu0

ま、理屈から言えばなるほどかもしらんが
瞬時に閃くのは数学脳やろ。をれ物理のひとやもん。

0052 名無しさん 2024/01/09(火) 11:30:39.01 ID:jq+lL+re0

何に使うの？プッチ神父以外使えることあるの？

0055 名無しさん 2024/01/09(火) 11:31:35.17 ID:kUq9ArLu0

>>52
銀行の暗号に、素数を使う。どのように使うかは、バラさないほうがいいとおもう。

0054 名無しさん 2024/01/09(火) 11:31:33.50 ID:M5d1EdwK0

テトリスなら

0056 名無しさん 2024/01/09(火) 11:31:36.05 ID:SzSuQ4yX0

ユニバーサルメルカトル図法を使うアレね

0058 名無しさん 2024/01/09(火) 11:32:38.62 ID:019/PoNU0

小さいほうから素数の倍数を順々に消していって、残ったのが素数ってだけだよな？
fizzbuzzより少し難しいくらいかな

0063 名無しさん 2024/01/09(火) 11:34:38.08 ID:kUq9ArLu0

>>58
しかしな～
どうやって、素数を、保存する？
配列にするとよ
オーバーフローすることがあるね。

だから、奇数で、やったはず。

0059 名無しさん 2024/01/09(火) 11:32:58.65 ID:kC/lhfwVM

ハノイの塔
なら工業高校のC言語の授業で作らされた

0061 名無しさん 2024/01/09(火) 11:33:44.39 ID:FsqtevSlH

まず篩が読めないケンモメンが5割

0062 名無しさん 2024/01/09(火) 11:34:10.67 ID:qeu6Lbhx0

ハイハイ、フィボナッチ数列ね

0067 名無しさん 2024/01/09(火) 11:36:31.72 ID:kUq9ArLu0

動くやつを書けよ、ばかだな。

0068 名無しさん 2024/01/09(火) 11:37:42.94 ID:Kl/H/fGU0

俺は大先生

0069 名無しさん 2024/01/09(火) 11:38:05.17 ID:kUq9ArLu0

マシン語、アセンブリ言語ならね。

素数、ガンガン、メモリの限り保存していって
回帰、再帰？で、組めるかもね。

0070 名無しさん 2024/01/09(火) 11:38:48.64 ID:kUq9ArLu0

高級言語だとね、配列って、ふつう、結構、低い数値までで限界なのよ。

0071 名無しさん 2024/01/09(火) 11:40:01.09 ID:lkd5e4p40

ChatGPTに書かせろっていうけど、普通にめちゃくちゃなコード出してくるからなあ
デバッグ能力がないと使えんぞ
大して長いコードも書けないし、うーん、毎月3000円も出して使うもんじゃない印象

0072 名無しさん 2024/01/09(火) 11:41:31.22 ID:kUq9ArLu0

をれ五十五歳なるからさ今年。

方針立てれるのは童貞だからだぜたぶん。

0073 名無しさん 2024/01/09(火) 11:44:05.49 ID:0n826j900

あー、エラテネね
よ、よゆーだしぃ

0074 名無しさん 2024/01/09(火) 11:47:28.27 ID:iRjbEefW0

プリミティブなＢＡＳＩＣだと、配列、ｎ（２５５）まで、のことあるんじゃない？

0075 名無しさん 2024/01/09(火) 11:48:17.29 ID:iRjbEefW0

そうすっと、

“そのやりかたでは”、

せいぜい、七桁くらいまでの素数しか出せないよ。

0077 名無しさん 2024/01/09(火) 11:50:32.32 ID:gFlbzYI06

そういえばFX702Pで2^172-1だかが素数かを調べる話読んだな
一晩かかるらしい

0104 名無しさん 2024/01/09(火) 14:04:14.23 ID:E+eC6R8V0

>>77
上付き文字使って 2¹⁷² – 1って書いたほうが読みやすいよ

0107 名無しさん 2024/01/09(火) 17:07:26.58 ID:2mSFi5Cm0

>>77
172が素数じゃない時点で

0078 名無しさん 2024/01/09(火) 11:52:17.47 ID:/HtYGZK+0

余裕でできるよ
それよりエビアンボルビックできんの？

0079 名無しさん 2024/01/09(火) 11:54:11.22 ID:gFlbzYI06

これだった素因数分解か
tps://www.asahi-net.or.jp/~kc2h-msm/pbsb/pbsbm003.htm

0080 名無しさん 2024/01/09(火) 11:58:54.25 ID:Fv3zzT7kM

ChatGPTよりGitHub Copilotのほうがいいよ

0081 名無しさん 2024/01/09(火) 11:59:17.86 ID:0CpkSeH10

AAAABBBCCこういった文字列を文字を並び替えて
全種類を辞書順に書き出す処理を
自力で書いたら思ったよりめんどくさかった

0082 名無しさん 2024/01/09(火) 12:05:06.41 ID:d8BMYmDe0

10print “エラトステネスの篩”

run

0083 名無しさん 2024/01/09(火) 12:06:04.41 ID:batnOAzZ0

かけないやつとかいるのか？

0084 名無しさん 2024/01/09(火) 12:07:43.41 ID:25Di8OMf0

整数の表を作って素数の倍数にバッテン付けて
最後にバッテンの付いていない数値を列挙するだけ
なら小学生でも書けるよな

0085 名無しさん 2024/01/09(火) 12:09:14.14 ID:xihJ8bDfr

書けるけど余白がなんたらかんたら
div 2とcmp後に
div [3+2n] とcmpを貰った数値まで繰り返せばいいの？
除算だしなんか○ぬほど時間かかりそうだけど

0086 名無しさん 2024/01/09(火) 12:27:24.71 ID:fkQyW8dX0

アルゴリズムを知っているかまたは自力で調べられるかどうかでプログラムの記述的には対して複雑じゃないよなこれって

0087 名無しさん 2024/01/09(火) 12:54:55.20 ID:+dcSfvUC0

ああエラ…鰤な
わかる

0088 名無しさん 2024/01/09(火) 13:01:48.17 ID:25Di8OMf0

桁溢れしない範囲で大まかにこんな感じのコードだね
スマホでアセンブラ打つの面倒
:begin
mov BX, (3-1) ; 3〜maxNを篩の対象とする
:loop1
inc BX
cmp BX, maxN ; 検査対象BX > maxNならループ1終了
jns end1
mov DX, 0 ; 検査対象BXの素数倍(DX)を篩落とす
:loop2
inc DX
mov CX, DX
cmp sieve[CX], 1 ; 既知の素数である事を確認
jz loop2
mov AX, BX
mul AX, DX
mov CX, AX
cmp CX, maxN ; 検査対象の素数倍 > maxN もしくは乗算が桁溢れならループ2終了
jc end2
jns loop2
mov sieve[CX], 1 ; 検査対象の素数倍をマーキング
:end2
jmp loop1
:end1
call printresult

0089 名無しさん 2024/01/09(火) 13:12:07.81 ID:+4BFS9AQ0

msgbox(“アリストテレスの鰤”)

0090 名無しさん 2024/01/09(火) 13:15:25.59 ID:eYN+qWIA0

昼ごはん前には食べちゃダメな奴だよな知ってる知ってる

0092 名無しさん 2024/01/09(火) 13:19:16.17 ID:9T6D9cPX0

for i=2 to 99999
for j=2 to sqrt(i)
if mod(i,j)=0 then break
next
result[]=i
next

0095 名無しさん 2024/01/09(火) 13:22:52.57 ID:25Di8OMf0

>>92
正解

0093 名無しさん 2024/01/09(火) 13:19:30.89 ID:pw/IaMdLH

簡単すぎるだろ
ハノイの塔くらいの難度でないとドヤれないだろ

0101 名無しさん 2024/01/09(火) 13:44:51.63 ID:HpyWn0v70

>>93
再帰関数で組んでくスキルがあると
割と簡単に書ける奴だよね
言語によっては学部コンピュータ実技の教科書で出てくるような練習課題程度

0097 名無しさん 2024/01/09(火) 13:34:51.01 ID:FDPb/8HR0

実際に使えるアプリケーションを書き上げる能力って測る方法あるんかな
AtCoderなんかで測れるのは極めて理数に振り切った能力でしかないし

0103 名無しさん 2024/01/09(火) 13:59:00.36 ID:nzlbQTEA0

>>97
ギフハブ見せてでいいんじゃね？
スター3桁あればおｋ

0098 名無しさん 2024/01/09(火) 13:38:35.79 ID:25Di8OMf0

理数系に振り切っててええやん
業務アプリなんて接客業だぞ

0102 名無しさん 2024/01/09(火) 13:55:41.48 ID:FDPb/8HR0

>>98
現実はそううまく行かないんだよなあ

0105 名無しさん 2024/01/09(火) 14:15:59.63 ID:qJYakwOzM

チェックするのはルートｎまで
高校数学の教科書に証明例題が出てただろ

0106 名無しさん 2024/01/09(火) 16:25:52.04 ID:TFIhhwtNd

職業SEで未だにコードも書くけど
その篩とやらの説明を読んでも何言ってるかよくわからない
もちろん書いてあるとおりにアルゴリズムを実装するのはできるだけろうけど

0109 名無しさん 2024/01/09(火) 17:26:12.62 ID:AH8B5OlD0

(ヽ´ん`)…エネ、エネマグラの棘？

参照先 https://greta.5ch.net/test/read.cgi/poverty/1704765678/\n\n