素数の見分け方

いっけん素数にしか見えないような数を、素数ではないとすばやく判断する方法ってあるのでしょうか？

たとえば、８４１という数は、２でも３でも４でも・・・・・・割れず、順順に判断していっても、なかなか割り切れません。結局、根拠なく素数だと判断してしまいます。

ですが、実際は ８４１＝２９×２９ なので、素数ではありません。

まともに考えていては、時間が足りないと思うのですが・・・何かうまい方法があるのでしょか？今日も、模試でこの問題が出て、だまされました（＞＜）

数学に詳しい方、ご教授ください。

No.10 ベストアンサー 回答者： Tacosan 回答日時： 2006/04/03 14:00

一応「決定論的な多項式時間素数判定アルゴリズム」は存在します. 与えられた n (log n ビットで表してます) が素数かどうかを, (log n)^8 くらいの計算時間で判定するというものだったような....

まあ n が小さければ √n までの数で割ってみるのが簡単かと.

No.9 回答者： noname#110252 回答日時： 2006/04/03 01:22

√nよりも小さな素数で割るか、#8さんが教えてくれた「フェルマーの小定理」を使うのが面倒かもしれないけど確実な方法だと思いますが、ある数が素数でないことをある程度まで絞ることはできます。

イ：10以上の数において、1の位が1・3・7・9でない場合は、その数は素数ではありません。

ロ：同じく10以上の数において、数字を一番上の位から1の位まで足していったとき、それが3の倍数になる場合は3で割り切れますので、素数ではありません。
例：6561の場合、使われている数字を全て足せば6+5+6+1=18となります。18=3*6で3の倍数ですので、素数ではありません。

このように、素数でないことを判別するテクニックは少しならありますので、活用してみてください。

No.8 回答者： proto 回答日時： 2006/04/02 20:08

フェルマーの小定理を用いた判定法があります。

pがもし素数ならば。
p以下の自然数mをなんでもいいので持ってきて、
mをp乗してpで割ると必ずm余ります。

式を用いて書くと。
　　m^p≡m (mod p)
になります。

なので、余りがmでなければpは素数でないことになります。
しかし余りがmならばpは素数かというと、そうとは限りません。
素数ではないkに対しても、
mのk乗をkで割った余りが偶然mになることはあります。

なのでp以下の自然数mについていろいろなmで
　　m^p≡m (mod p)
になるか試してみて、成り立たなければpは素数でないことになります。

この方法は√p以下の自然数で実際に割っていくよりも効率的な方法です。
しかし、カーマイケル数と名前の付いた素数もどきの合成数が存在するので注意が必要です。
カーマイケル数に対しては上記以外の確実な判定法もあります。
そちらは初心者には少し難しいですが。

参考URL：http://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A7% …

No.7 回答者： Ama430 回答日時： 2006/04/02 10:34

みなさんの書かれている方法しかないために、大きな素数の扱いはコンピュータを使っても時間がかかります。

そのために素数が暗号に利用されていると聞いたことがあります。

No.6 回答者： tatsumi01 回答日時： 2006/04/02 01:35

脇道にそれます。

Ｎが素数かどうかを判定する高速な方法もあるようですが、Ｎを√Ｎ以下の素数で割ってみる方法が確実です。
√Ｎ以下の素数はどれ位あるかというと、ざっと√Ｎ／（１．１５・ｌｏｇ（Ｎ））ですから、この回数分の割り算が必要です（ｌｏｇは常用対数）。
このとき、√Ｎ以下の素数で割るとき、素数表を覚えておかないといけません。覚えていないと、ある整数Ｋで割るとき、Ｋが素数かどうか判定しないといけません。そんなことを判定しているより、素数かどうか関係なく２から順に割っていった方が早いでしょう。
素数表を覚えていないと√Ｎ回の割り算が必要です。Ｎ＝８４１とすると、必要な割り算の回数は、素数表を覚えていれば１０回、覚えていなければ２９回です。
以上から、教訓として「１００以下の素数は覚えておいて損はない」です。１００以下の素数は２５個ですから覚えるのは大した手間ではありません。
それから３０以下の整数の二乗も覚えておいて損はありません。実際、私は８４１と見た途端に２９の二乗とわかりました。

No.5 回答者： yoikagari 回答日時： 2006/04/01 22:06

ある数nが素数あるかどうか調べる方法は、√nよりも小さな素数で割ってみるしかありません。

(ほかの判定法もありますが、大学の数学科で勉強する内容になりますし、どれも上記の方法より効率が悪いものです)
この問題の場合n=841ですから、√841=29以下の素数2,3,5,・・・,29で割ってみるしかありません。
その際に、下記の倍数の判定が多少役に立つと思います。
たとえば
「nの1の位が偶数なら、nは2で割り切れます。」
「nの1の位が0あるいは5なら、nは5で割り切れます。」
「nの各位の和が3の倍数ならば、元の数も3で割り切れる。」
といった判定法を知っておくと多少計算は楽になります。

参考URL：http://www004.upp.so-net.ne.jp/s_honma/number/mu …

No.4 回答者： agosu 回答日時： 2006/04/01 21:27

私が現役の時は１の位に注目してました。

例えば質問の８４１の１の位は１です。１の位が１になる１桁の掛け算は１＊１と３＊７と９＊９のみです。（７＊３は３＊７と一緒として）あとは上の３つの式に１０の位を当てはめていきます。この方法ならだいぶ考えるのが楽になりますよ。

No.3 回答者： noname#16546 回答日時： 2006/04/01 21:24

開平計算という計算があるのですが、学校で習わないですよね。

でも実際はこれを使わないと解けない問題もたまにあると思うので、覚えておくといいと思います。(この計算を使うと841が29の2乗であることもスグわかります)
解説したＵＲＬがあったので貼っておきますね。わかりにくかったら、数学の先生に質問したら教えて下さると思いますよ。何回か手を動かして計算したらすぐ覚えられます。

偶然にも、私も841が見破れなかったことをきっかけに、姉に教わって覚えました。これもご縁です、覚えちゃってください(^^)

参考URL：http://www004.upp.so-net.ne.jp/s_honma/root.htm

No.2 回答者： driverII 回答日時： 2006/04/01 21:19

確率的素数判定法というのが早いようですが・・・

nの素数判定の場合、

3からルートｎまでの素数について割り算を行えば良いのですから、試験であれば大丈夫ですよね・・・

参考URL：http://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0% …

No.1 回答者： tnt 回答日時： 2006/04/01 21:09

その数のルートを取り、その数字よりも小さいすべての

素数で割ってみて、
あまりが出ない物があったら素数ではない。

他に方法は無いと思います。