素数かどうかを知るには（手順）

ある数、とくに何桁もの数が素数かどうかを知るにはどんな手順がありますか？

私は（１）その数が１０の倍数かどうか（２）２の倍数かどうか（３）９の倍数かどうか
しかわかりません。
（３）は、各桁の番号を足してそれが９の倍数なら９で割り切れるということです。

他の有効な手順があれば教えてください。

No.10 ベストアンサー 回答者： chiropy 回答日時： 2006/10/16 17:57

一応素数を求める（かどうか判断する）式？は存在するそうです。

何かの本で読みました。ただ例えば1000までの素数を書き出すのに自分の手を動かせば数時間もあればできるでしょう。しかしこの式を使うとコンピュータでやっても何日もかかるそうです。つまり式は存在するが実用的ではないのです。
でご質問の答えですが「エラトステレスの篩」を利用するのが適当ではないでしょうか？これは『ある数nが素数かどうか判断するとき√n以下の素数でnを割ったとき割り切れるものがなければそのnは素数である。』と判断できる方法です。

例えば953が素数かどうかを判断するなら√953=30.087…ですから
2,3,5,7,11,13,17,19,23,29の10個の数で割ってやるだけで判断できます。

No.9 回答者： sak_sak 回答日時： 2006/10/13 23:14

#6さんの言われている「その数の１／２以下の整数」は

「√(その数)以下の自然数」の誤りだと思います。
もちろん1で割っても仕方がないですが。

個人的に素数かどうか判別したいなら
mathematicaやmaximaなどのソフトを使う方法もあります。

No.8 回答者： moritan2 回答日時： 2006/10/13 19:31

公開鍵暗号につかうような１００桁以上の数字が素数かどうか判定するには、アドレマン－ルメリーのアルゴリズムを用います、これで百数十桁の整数なら数秒で素数かどうか判定できます。

[アドレマン 素数]でgoogleで検索すればたくさん引っかかるでしょう。

No.7 回答者： kumoringo 回答日時： 2006/10/13 17:02

参考URLをどうぞ。

ウィキペディアの「素数判定」の項目です。

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

No.6 回答者： Willyt 回答日時： 2006/10/13 16:56

その数の１／２以下の整数で片端から割って見るよりないですね。

No.5 回答者： tokyowave 回答日時： 2006/10/13 16:44

ある数が、素数であるかどうかの判定方法は、存在しません。

質問者の方が仰られるように、１０の倍数や９の倍数、偶数かどうか
などは、すぐ判定は出来るのですが、素数に関しては未だ存在していないのです。
素数かどうか判定できる公式を発見できれば、数学界のノーベル賞とも言われるフィールズ賞間違いなし、ですね。

ちなみに、つい最近、アメリカの研究者により最大の素数が発見されたようです。
下記のURLをご覧ください。

参考URL：http://news.livedoor.com/webapp/journal/cid__160 …

No.4 回答者： neKo_deux 回答日時： 2006/10/13 16:43

エラストテネスのふるいという方法ですと、

数字の表を用意します。
2の倍数は素数である事が分かっているので、01～２飛ばしです。
1は素数なので、--を付けときます。
-- 03 05 07 09 11 13 15 17 19
21 23 25 27 29 31 33 35 37 39
41 43 45 47 49 51 53 55 57 59
61 63 65 67 69 71 73 75 77 79
81 83 85 87 89 91 93 95 97 99

表で塗りつぶされていない一番若い03が素数です。
03の倍数を--で塗りつぶします。
-- -- 05 07 -- 11 13 -- 17 19
-- 23 25 -- 29 31 -- 35 37 --
41 43 -- 47 49 -- 53 55 -- 59
61 -- 65 67 -- 71 73 -- 77 79
-- 83 85 -- 89 91 -- 95 97 --

表で塗りつぶされていない一番若い05が素数です。
05の倍数を--で塗りつぶします。
-- -- -- 07 -- 11 13 -- 17 19
-- 23 -- -- 29 31 -- 35 37 --
41 43 -- 47 49 -- 53 -- -- 59
61 -- -- 67 -- 71 73 -- 77 79
-- 83 -- -- 89 91 -- -- 97 --

表で塗りつぶされていない一番若い07が素数です。
07の倍数を--で塗りつぶします。
-- -- -- -- -- 11 13 -- 17 19
-- 23 -- -- 29 31 -- -- 37 --
41 43 -- 47 -- -- 53 -- -- 59
61 -- -- 67 -- 71 73 -- -- 79
-- 83 -- -- 89 -- -- -- 97 --

同様に、11が素数、13が素数と、表を塗りつぶす事で、表の中に含まれる素数が分かります。
求める数字が素数かどうかは、その数字までの表が必要になります。

コンピュータでやるのなら、2～その数(の平方根)までで片っ端から割り算して、割り切れる数があるかどうかを調べるだけですが…。

No.3 回答者： Mister0413 回答日時： 2006/10/13 16:43

他には（１）の延長として（４）、（３）の延長として（５）があります。

他には１１や１００１を疑ってみることくらいでしょうか。問題演習の場面では、１１で割り切れる場合って意外と多いですよ。
他の方が回答されていてるように、その数の平方根まで（例えばその数が１００ならばルート１００、つまり１０まで。その数が４００ならばルート４００、つまり２０まで）疑ってみる必要があります。
（４）一の位が５であれば５の倍数である
（５）各桁の番号を足してそれが３の倍数なら３で割り切れる

少し手間がかかりますが、数学的に立証された本格的な見つけ方としては「エラストテネスのふるい」が有名です。これに関する詳しい説明については、参考サイトをご覧下さい。

参考URL：http://macky0625.hp.infoseek.co.jp/sosuu.htm

No.2 回答者： finneganswake 回答日時： 2006/10/13 16:33

そうやっていくしかないよ。

2で割って、3で割って…と素数で割っていくしか確かめる方法がない。（その数のルートまでね。それを超えたら相手がいるはずだから。）

No.1 回答者： chie65536 回答日時： 2006/10/13 16:30

ある数が偶数の場合、素数ではないのが自明なので除外して、３から順に奇数で割っていくしかない。

この時、明らかに無駄と思える数で割るのは除外する。例えば９とか１５とか。３や５で割り切れないと判明した時点で９とか１５とかでは割り切れないのは明らか。

割る数を大きくして行き、それが「ある数」の平方根を超えたら、素数であると言える。