素数判定の使い方

質問

数学A整数の性質について質問です。
素数判定についての質問なのですが、
素数判定というのは、この問題のカッコ１にあるように、基本的な倍数判定（2,3,4,5,9など）はしたうえで√N以下の素数で割るという動作をするということであっているでしょうか?
基本的な倍数判定が通じなかった⇒√N以下の素数で素数判定
であっているでしょうか?教えてください。

回答No.3

staratras · ベストアンサー

>素数判定というのは、この問題のカッコ１にあるように、基本的な倍数判定（2,3,4,5,9など）はしたうえで√N以下の素数で割るという動作をするということであっているでしょうか?

2以外の偶数はすべて合成数であり素数ではないということを理解していれば、4の倍数判定は必要なく、また9の倍数は3の倍数に含まれることは明らかだから9の倍数判定も不要です。

お礼

やっぱりそうでしたか。。 学校で先生にも教えてもらって、4や9は2や3の倍数だからと言われて、ああそうか。と思いました。 わかりやすかったです!ありがとうございます!

Powered by GRATICA

回答No.4

maskoto

要領良いやり方は、次のようになります

1(貴方の言う、基本的判定をまず試みる)
そのためには、
・a　…Nの一の位が偶数かどうか見る(一の位＝0も偶数とみなす)
→一の位が偶数なら、N自体も偶数で
Nは因数の一つに素数2を持つことになる
→この判定を試みて一の位＝偶数だった場合、Nを2で割り算したら、割り切れたと言う事と同じである…①

・b…Nの各桁を足し算して、和が3の倍数になっているかチェック
→和が3の倍数なら、Nも3の倍数であり
Nは因数の一つに素数3を持つことになる
→この判定を試みた場合、Nを3で割り算して割り切れるか確認する事と同じ…②

・c…　Nの一の位が5になついるかチェック
→一の位が5なら、Nは素数5を持つ
→この判定を試みれば、Nを5で割り算してみる事と同じ…③

・d…　Nの各桁を一つおきに確かして
イコールになっているかチェック
例、N＝１243なら、一つおきに足し算するとは
1+4＝5
2+3＝5
というようにして見る事
今回は　ともに5となり、イコールになっている
→イコールになるような数は11で割り切れるから、素数11をもつ
→この判定をした場合は、Nを11で割り算してみる事と同じ…④

・4、9などの素数でない数に関する判定は無意味なので行わない

上記を試みた上でまだ、Nが素数かどうかわからない場合は
√N云々の判定に移ります！
ただし、①〜④に記したように
上記の判定により
N÷2、N÷3、N÷5、N÷11
の割り算は試みたに等しいので
√N以下の素数での割り算を試みるとき
2、3、5、11での割り算はスキップして
素数7、素数13、素数17…の割り算だけ試みれば良い事になります

お礼

詳しくありがとうございます！ 素因数分解がちんぷんかんぷんで以前は適当に聞き流してたところがあったんですけど、 ようやく理解できました。 自分の前の考え方から一新できたと思います。ありがとうございます。

Powered by GRATICA

回答No.2

chie65536（@chie65535）

＞素数判定というのは、この問題のカッコ１にあるように、基本的な倍数判定（2,3,4,5,9など）はしたうえで√N以下の素数で割るという動作をするということであっているでしょうか?

微妙に違います。

２から順に、√N以下の素数で割ってみる

が正しいです。

57の場合、√57は約7.55なので、２、３、５、７で割ってみる。

89の場合、√89は約9.434なので、２、３、５、７で割ってみる。

247の場合、√247は約15.71なので、２、３、５、７、１１、１３で割ってみる。

383の場合、√383は約19.57なので、２、３、５、７、１１、１３、１７、１９で割ってみる。

ですが、事実上「２で割ってみる」は試す必要がありません。１の桁が偶数ならば必ず２の倍数なので、割ってみる必要はなく、合成数なのは明らかです。

解答の（１）に「５＋７＝１２は３の倍数なので」の部分について。

百の位がA、十の位がB、一の位がCの３桁の整数「ABC」を、A、B、Cを使った式で書くと

A×１００＋B×１０＋C

になります。

１００は９９＋１に、１０は９＋１に変形出来るので、上記の式は

A×（９９＋１）＋B×（９＋１）＋C

になり、更に変形すると

A×９９＋B×９＋A＋B＋C

になります。

更に変形すると

３（A×３３＋B×３）＋A＋B＋C

になります。

この式の「３（A×３３＋B×３）」の部分は「必ず３の倍数」です。ですので、残りの「A＋B＋C」が３の倍数になれば「３の倍数＋３の倍数＝３の倍数」なので、式全体が３の倍数になります。

なので「各桁の数値を全部足したもの（つまりA＋B＋C）が３の倍数なら、３桁の数値ABCも３の倍数」になります。

これは、２桁でも４桁でも、それ以上の桁数でも成り立ちます。

ですので「５＋７＝１２は３の倍数なので」という事になります。

お礼

遅くなりましたが、確かに自分も微妙に違うなって今思いました。 素因数分解は奥が深いですね。 勉強するといろんな性質につながりますからね。 それはさておき、ありがとうございました。

Powered by GRATICA

回答No.1

SI299792

そうですね。
順番に√N の素数で割っていけば、素数かどうかわかります。

例えば53
√53＝7.･･･
（小数迄出す必要はない。7²=49 から簡単に出る。）
2 3 5 7 迄素数で割っていき、全てで割り切ないから素数とをわかります。
しかし、ぱっと見で素数でないと解れば（偶数等はすぐわかる）一々このような計算をせず、素数でないと判断した方が早いです。

お礼

遅くなりました。回答ありがとうございます。 ルートでの判別って、意外に勉強を進めると便利ですね。

Powered by GRATICA