素数の判定方法？を教えて下さい。

質問

素数(31) に30ずつプラスしていって、下記の様に３１個並べた時いずれが素数に成るかどうか
( 31)を上手に使って、証明する方法がありましたら、ご教授下さい。

　　　　31 ,61,91,121,151,181,211,241,271,301,331,361,391,421,451,481,511,541,571,601,631,661,691,
721,751,781,811,841,871,901,

回答No.3

nag0720 · ベストアンサー

３１個並べたら最後は931になるはずだけど、記載もれ？

末尾が１になる掛け算は、
(10n+1)(10m+1)=10(10nm+n+m)+1
(10n+3)(10m-3)=10(10nm-3n+3m-1)+1
(10n-1)(10m-1)=10(10nm-n-m)+1

10nm+n+m、10nm-3n+3m-1、10nm-n-mが3の倍数で3以上93以下となるのは次の１４個
(1,1)=12,(1,4)=45,(1,7)=78
(1,1)=9,(1,4)=48,(1,7)=87,(2,2)=39,(4,1)=30,(5,2)=90,(7,1)=51,(10,1)=72,(13,1)=93
(2,2)=36,(2,5)=93（既出）,(3,3)=84

これ以外の１７個が素数となる。
31,61,151,181,211,241,271,331,421,541,571,601,631,661,691,751,811

検証はしていませんので、あしからず。

お礼

アッ一個抜けていました。すみません。　　　　　　　　　　　式を立てて頂きありがとうございました。　　　　　　　　　　　ベストアンサーにさせて頂きます。

回答No.5

birth11

No.4です。プログラム、時間がかかりすぎで、答えが中々出ません。申しわけありませんが、give up
です。

お礼

ギブアップさせてすみません。
　　　　ありがとうございました。

回答No.4

birth11

81 = 3 * 27 は素数でないが表の中に含まれていないので論外。
891 = 81 * 11 は素数でないが表の中に含まれていないので論外。
261 = 9 * 29 は素数でないが表の中に含まれていないので論外。
261 * 11 > 901であるので、これ以上考えない。
91 = 7 * 13 は素数でない。
91 * 11 = 1001 > 901 であるので、これ以上考えない。
7 * 23 = 161 は素数でないが表の中に含まれていないので論外。
161 * 11 > 901 であるので、これ以上考えない。
121 = 11 * 11 は素数でない。
121 * 11 > 901 であるので、これ以上考えない。
13 * 17 = 221 は素数でないが表の中に含まれていないので論外。
221 * 11 > 901 であるので、これ以上考えない。
19 * 19 = 361 は素数でない。
361 * 11 > 901 であるので、これ以上は考えない。
21 * 21 = 441 は素数でないが表の中に含まれていないので論外。
441 * 11 > 901 であるので、これ以上考えない。
341 = 31 * 11 は素数でないが表の中に含まれていないので論外。
341 * 11 > 901 であるので、これ以上考えない。
29 * 29 = 841 素数でない。
841 * 11 > 901 であるので、これ以上考えない。
………………………
素数であるか素数でないか、コンピューターにかけてくれ。
BASIC 言語 プログラム
10 clear
20 dim a(31)
30 for n = 1 to 31
40 t = 30 * n + 1
50 for I= 2 to 15 * n
60 a( n )= t
70 if int( t / I ) * i = t then a( n ) = 0: I= 31
80 next I
90 next n
100 for I= 1 to 31
110 if a( I ) <> then print a( I );" は素数である。" else print I;"は素数でない。"
120 next I
130 end

これで結果が出ると思います。
（３１）を上手に使えなくてごめんなさい。

お礼

ありがとうございました。お礼がたいへん遅れて申し訳ございません。

回答No.2

angkor_h

素人で申し訳ありませんが、

数列は、[30n+1}n=1-30　のようになると思います。
末尾が常に1なので、除数になり得ない数は、2,3,4,5,6,8,9
除数になり得るのは末尾が1となる、7x3=21の7
なので、21を引いた時に残る数が7の倍数ならば…301、511、
結局は、[7x(10m+3)]m=0-　に一致するか否か、

これではダメ?

お礼

ありがとうございました。

　　　　　(151－21)/7 ?

回答No.1

Tacosan

あんまりうまい方法はないんじゃないかな. エラトステネスのふるいのようにやるのが結局最も速い気がします.

お礼

ありがとうございました。