暗算で素数判定する方法を模索するスレ [転載禁止]©5ch.io
■ このスレッドは過去ログ倉庫に格納されています
0001１３２人目の素数さん
2015/11/03(火) 14:59:37.64ID:r4dqWRS27*11*13=1001なので、nと1001の最大公約数を求めれば、7,11,13の倍数判定が一挙にできる。
例：n=2357
(2357,1001)=(355,1001)=(5*71,1001)=1
1001が1000に近いので暗算しやすいのがポイント。
このように、素数判定（の過程における計算）を暗算で効率よくおこなう方法を書き込むスレです。
細かい計算テクニックや、全く別の考え方による方法も含めて模索していきましょう。
0002１３２人目の素数さん
2015/11/03(火) 15:03:30.00ID:5PrOATAK0003１３２人目の素数さん
2015/11/03(火) 15:42:45.09ID:cjjUqiTH〈〈〈 ヽ
〈⊃ }
∩＿＿＿∩ | |
| ノ ヽ ! !
/ ● ● | /
| ( _●_) ミ／ こいつ最高にアホ
彡､ |∪| ／
/ ＿＿ ヽノ /
(＿＿＿） /
∩＿＿＿∩
| ノ ヽ
/ ● ● | こいつすげぇアホ！！
| ( _●_) ミ
彡､ |∪| / ＼
/ ＿＿ ヽノ / ＼ ＼
(＿＿＿） / │ │
│ │
/ ヽ
l lUUU
Ｕ
0004１３２人目の素数さん
2015/11/03(火) 16:15:47.05ID:uPVICE7l└――――――――┘
0005１３２人目の素数さん
2015/11/03(火) 18:44:29.36ID:r4dqWRS2より多くの素数を暗記すれば、暗算で素数判定できる数の範囲が広がりますね。
効率良く暗記する方法も考えていきたいと思います。
語呂合わせが基本になるでしょうか。
バナナはおやつに入りませんが877は素数に入るそうです。
また、いくつかの素数を関連付けてまとめて覚えられれば効率的です。
57の頭または末尾に数字を1つ付け加えたもののうち2,3,5の倍数でないものは素数になります。
すなわち157,257,457,557,571,577,757,857は素数です。
他にもこのような性質をもつ2桁の数があればいいのでやすが、残念ながら57のみです。
101,103,107,109や191,193,197,199のような4つ子素数も覚えやすい。
他にもいろいろあると思うので、しょうもない語呂合わせでもいいので書いてもらえればと思います。
0006１３２人目の素数さん
2015/11/03(火) 18:55:23.23ID:DahdgIPOこれすごい
0007１３２人目の素数さん
2015/11/03(火) 20:27:44.54ID:xtFptD+n開 幕 だ
ｎ: ＿＿＿ ｎ:
|｜ ／ ＿＿ ＼ .|｜
|｜ | |(ﾟ) (ﾟ)| | |｜
ｆ｢| |^ﾄ ヽ ￣￣￣ / ｢| |^|`|
|: :: ! ] ￣□￣ | ! : ::]
ヽ ,ｲ ／￣￣ハ￣￣＼ ヽ ｲ
0008１３２人目の素数さん
2015/11/03(火) 22:58:10.63ID:r4dqWRS2＞他にもこのような性質をもつ2桁の数があればいいのでやすが、残念ながら57のみです。
奇数しか考えていなかったので見逃していたのですが、82も当てはまります。
つまり821,823,827,829は素数。
3桁の4つ子素数は>>5で書いたものとこれらの3組しかありません。
>>6
ありがとうございます。
1003=17*59
1007=19*53
2001=3*23*29
も使えると思います。
2021=43*47も使えるときは使えるやつです。
あと、複数の素数をまとめて判定というのではないですが、
999=3^3*37
111=3*37
100a+10b+cが37の倍数ならば100b+10c+aも37の倍数
これらを使うだけで37の倍数判定ができます。
0009１３２人目の素数さん
2015/11/05(木) 00:31:17.52ID:KHEakpxjnとmの最大公約数(n,m)について一般に次のことが成り立ちます。
aはmと互いに素な整数、bは任意の整数として
(n,m)=(an+bm,m)
とくに
(n,m)=(an,m)
これを逆向きにすれば
(an,m)=(n,m)
これらを利用してnを簡単な数に変形していくことができます。
mは2でも5でも割り切れない数とします。
特に覚えておくべき方法は次のようなものです。
(1) an+bmの1の位が0なるようにする。
(2) それを10で割る。
nの桁数が大きいとき、この方法で桁数を減らせます。
例：(2357,1003)=(2357+1003,1003)=(3360,1003)=(336,1003)=(3*2*56,1003)=1
ちなみに(2357,1003)=(2357-2*1003,1003)=(351,1003)としても桁数が減ります。
このあと351を分解してもいいですが
(351,1003)=(351*3,1003)=(1053,1003)=(50,1003)=1
とする手もあります。
例2：(839,1003)=(1003*3-839,1003)=(2170,1003)=(217,1003)=(7*31,1003)=1
839は分かりにくい数なので、別の3桁の数に変形してみたら分かりやすくなったわけです。
この例の場合は1003-839=164としたほうが簡単かもしれませんが…。
さらにいえば839は素数と知っていれば無駄な計算なのでした。
0010１３２人目の素数さん
2015/11/06(金) 22:57:02.60ID:SzLFjJKd逆にnが合成数で奇数ならば、上記を満たすa,bが存在します。
nが大きくなるとこのようなa,bを探すのも大変です。
しかし、ある範囲にaが存在しないことが分かれば、nの素因数の範囲が絞れます。
ここで考えるべきことは2つ。
aの値の候補を絞るための簡単な方法。
そして、aの範囲が限定されたときnの素因数の範囲を求める簡単な方法です。
1つ目に関しては、modで考えると、ある程度aの値が絞れることが分かります。
2つ目は不等式を求めることはできるのですが、面倒です。
もう少しまとまったら、また書こうと思います。
0011１３２人目の素数さん
2015/11/08(日) 00:36:42.60ID:byozhffs529=23^2
667=23*29
713=23*31
841=29^2
851=23*37
943=23*41
899=29*31
961=31^2
989=23*43
の9つです。
これらを覚えておけば、3桁の整数については19以下の素数で割り切れるかどうかで素数判定できます。
平方数はすでに覚えているとすれば残りは6つです。
特に、nが3桁の整数で1の位が1の場合、素数判定は次のようになります。
(1) nが平方数ならば合成数
(2) n=851ならば合成数
(3) nの各桁の数字合計が3の倍数ならば合成数
nの末尾の1を消して得られる2桁の数をmとする
(4) 100-mが7,11,13のいずれかの倍数ならば合成数
(5) m-5が17の倍数ならば合成数
(6) m+2が19の倍数ならば合成数
これらのどれにも当てはまらなければ、nは素数となります。
こうして書いてみると結構面倒に見えるかもしれませんが、覚えておく価値はあると思います。
■ このスレッドは過去ログ倉庫に格納されています