回答受付が終了しました

ID非公開

2021/2/25 21:09

55回答

1000以下の素数は250個以下であることを示せ

数学503閲覧

1人が共感しています

回答(5件)

2

[1000/2]+[1000/3]+[1000/5]+[1000/7] -([1000/6]+[1000/10]+[1000/14]+[1000/15]+[1000/21]+[1000/35]) +([1000/30]+[1000/42]+[1000/70]+[1000/105]) -([1000/210]) =500+333+200+142-(166+100+71+66+47+28)+(33+23+14+9)-4 =772 (素数は250以下である)=(1か合成数が750個以上ある)なので、題意は示された ■ n=3のVenn図でやって、そこから少し数えてもよい (n=4のVenn図は楕円使わないと表現できない)

画像

2人がナイス!しています

1

1000以下の非素数を以下に750個挙げる ・1 ・2,3,5(←素数)を除く、1000以下の2または3または5の倍数…-3+500+333+200-166-66-100+33=731個 ・7×7,7×11,7×13,7×17,7×19,7×23,7×29,7×31,7×37,7×41,7×43,7×47,7×49=7×7×7,7×53,7×59,7×61,7×67,7×71 …18個 よって1000以下の自然数には少なくとも750個の非素数が含まれるので、1000以下の素数は250個以下である。 ※1は素数でも合成数でもない

1人がナイス!しています

1

210 を法に見ると φ(210) = 210・1/2・2/3・4/5・6/7 = 210・8/35 であることから、ちょうど210個の周期では素数の個数は 8/35 以下と言える。(何故なら210と互いに素でない数は素数ではあり得なく、すなわち素数が 8/35 以上あったとすると鳩ノ巣原理により矛盾する) 以上より 210・5 = 1050 の時点で素数の個数は 1050・8/35 = 240個以下が確定。よって題意は示せた。 オイラー関数については以下のリンクをご参照ください。。 https://ja.m.wikipedia.org/wiki/%E3%82%AA%E3%82%A4%E3%83%A9%E3%83%BC%E3%81%AE%CF%86%E9%96%A2%E6%95%B0 https://mathtrain.jp/phi

1人がナイス!しています

素数の分布は分からなくても、オイラー関数を使って「互いに素である数の個数」の分布は分かる事を利用したアイデアです。 φ(n) < 1/4・nであるような n を目安に方針に合うような自然数を探すと 210 が適しました。 それぞれにおいての特定の数を探す必要があると思うので、汎用性があるかは難しいですが。。

1

2の倍数が1000までで 1000/2=500個 2の倍数でない3の倍数 3・1,3,5,・・・333 333/2=166.5 167個 2,3の倍数じゃない5の倍数 5・1,5,・・・200 200-200/2-200/(2・3) =200-100-33 =64 64個 2,3,5の倍数じゃない7の倍数 7・1,7・・・ 1000/7=142 142-142/2-142/(2・3)-142/(2・3・5) =142-71-142/6-142/30 =71-23-4 =44 500+167+64+44 =775 だいたいこんな感じで解けると思う 細かいとこあってるかわからん^^;

1人がナイス!しています

1

合成数が少なくとも750個あることを示せれば良いので、2または3で割り切れる数がいくつあるかを数えればそれくらいの数になりそうな気がします。

1人がナイス!しています