![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?5a7ff87)
No.10ベストアンサー
- 回答日時:
一応素数を求める(かどうか判断する)式?は存在するそうです。
何かの本で読みました。ただ例えば1000までの素数を書き出すのに自分の手を動かせば数時間もあればできるでしょう。しかしこの式を使うとコンピュータでやっても何日もかかるそうです。つまり式は存在するが実用的ではないのです。でご質問の答えですが「エラトステレスの篩」を利用するのが適当ではないでしょうか?これは『ある数nが素数かどうか判断するとき√n以下の素数でnを割ったとき割り切れるものがなければそのnは素数である。』と判断できる方法です。
例えば953が素数かどうかを判断するなら√953=30.087…ですから
2,3,5,7,11,13,17,19,23,29の10個の数で割ってやるだけで判断できます。
No.9
- 回答日時:
#6さんの言われている「その数の1/2以下の整数」は
「√(その数)以下の自然数」の誤りだと思います。
もちろん1で割っても仕方がないですが。
個人的に素数かどうか判別したいなら
mathematicaやmaximaなどのソフトを使う方法もあります。
No.8
- 回答日時:
公開鍵暗号につかうような100桁以上の数字が素数かどうか判定するには、アドレマン-ルメリーのアルゴリズムを用います、これで百数十桁の整数なら数秒で素数かどうか判定できます。
[アドレマン 素数]でgoogleで検索すればたくさん引っかかるでしょう。No.7
- 回答日時:
No.5
- 回答日時:
ある数が、素数であるかどうかの判定方法は、存在しません。
質問者の方が仰られるように、10の倍数や9の倍数、偶数かどうか
などは、すぐ判定は出来るのですが、素数に関しては未だ存在していないのです。
素数かどうか判定できる公式を発見できれば、数学界のノーベル賞とも言われるフィールズ賞間違いなし、ですね。
ちなみに、つい最近、アメリカの研究者により最大の素数が発見されたようです。
下記のURLをご覧ください。
参考URL:http://news.livedoor.com/webapp/journal/cid__160 …
No.4
- 回答日時:
エラストテネスのふるいという方法ですと、
数字の表を用意します。
2の倍数は素数である事が分かっているので、01~2飛ばしです。
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
- 回答日時:
他には(1)の延長として(4)、(3)の延長として(5)があります。
他には11や1001を疑ってみることくらいでしょうか。問題演習の場面では、11で割り切れる場合って意外と多いですよ。他の方が回答されていてるように、その数の平方根まで(例えばその数が100ならばルート100、つまり10まで。その数が400ならばルート400、つまり20まで)疑ってみる必要があります。
(4)一の位が5であれば5の倍数である
(5)各桁の番号を足してそれが3の倍数なら3で割り切れる
少し手間がかかりますが、数学的に立証された本格的な見つけ方としては「エラストテネスのふるい」が有名です。これに関する詳しい説明については、参考サイトをご覧下さい。
参考URL:http://macky0625.hp.infoseek.co.jp/sosuu.htm
No.1
- 回答日時:
ある数が偶数の場合、素数ではないのが自明なので除外して、3から順に奇数で割っていくしかない。
この時、明らかに無駄と思える数で割るのは除外する。例えば9とか15とか。3や5で割り切れないと判明した時点で9とか15とかでは割り切れないのは明らか。
割る数を大きくして行き、それが「ある数」の平方根を超えたら、素数であると言える。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 【 数A 順列 】 問題 6個の数字0,1,2,3,4,5を使ってできる次の ような整数は何個あるか 1 2022/06/19 12:18
- 数学 数学の複素数の証明問題です。 (1)複素数全体の集合に2要素間の実数と同様な大小を定義できないことを 2 2022/08/28 11:17
- 数学 法則名ありますか? 2 2022/10/09 16:21
- 数学 最小公倍数と最大公約数の求め方で画像のような計算法があったのですが、理解できません。 なぜ2つ数24 4 2022/04/10 13:37
- 数学 中一数学の【最大公約数と最小公倍数】の問題です。 1問だけでも教えていただけると嬉しいです。 (1) 4 2022/08/01 10:19
- 数学 【 数A 集合の要素の個数 】 問題 100から200までの整数のうち, 5の倍数であるが,3の倍数 5 2022/07/18 13:33
- 統計学 都立入試 1 2022/10/11 19:43
- Excel(エクセル) エクセル、日々の集計整理方法。(再送です。) 5 2022/10/02 00:19
- 数学 nは正の整数であり、偶数。 n(n+1)(n+2)(n+3)は素因数が3つ。 nを求めよ。 という問 8 2022/09/26 18:15
- 数学 1から9の数字を書いたカードが一枚ずつある。これらの9枚のカードから同時に2枚を取り出し、数字の大き 5 2022/04/25 15:38
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
4?4?4?4=10の?に+-×÷( ...
-
0.75乗の計算方法(電卓を使って)
-
ルート7+ルート5+ルート7−ルー...
-
【至急】平方根の中の二乗につ...
-
ルート9はなぜ-3ではないのです...
-
インターネットでの数学の記号...
-
中3の応用問題
-
平方根の計算
-
1から100までの
-
√の中がマイナスになった時、i...
-
平方根の開平
-
ルートの語呂合わせ
-
数学に関する質問(中学~高校...
-
四分の三乗って?
-
ルート8 × ルート12
-
平方根の問題の解説をしてくだ...
-
2√10がなんで10何ですか? √100...
-
素数かどうかを知るには(手順)
-
根号のない形に表す
-
(√2+√5)² この式を計算しな...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
インターネットでの数学の記号...
-
0.75乗の計算方法(電卓を使って)
-
4?4?4?4=10の?に+-×÷( ...
-
【至急】平方根の中の二乗につ...
-
√の中がマイナスになった時、i...
-
ルート9はなぜ-3ではないのです...
-
四分の三乗って?
-
こっちの画像では45度のときル...
-
(√2+√5)² この式を計算しな...
-
昔のCMの歌詞
-
2√10がなんで10何ですか? √100...
-
ルート7+ルート5+ルート7−ルー...
-
勉強
-
累乗根の読み方
-
ルートの語呂合わせ
-
高校数1です。 【問】不等式ー√...
-
無理関数の極限の問題でどの式...
-
なんで 1/3=0.33333 なのに0.33...
-
ルートの中身は絶対、正 なのに...
-
根号のない形に表す
おすすめ情報