« 白梅 | トップページ | 333333331は素数か:2 »

2017年2月 3日 (金)

333333331は素数か:1

★朝日新聞木曜日の連載から

(福岡伸一の動的平衡:60)素数に魅せられて(朝日新聞デジタル 2017年1月26日05時00分)
 東急大井町線の電車の中で真面目そうな若者が2人話していた。「こんなの知っている? 31は素数、331、3331、33331も素数、これどんどん続くんだよ」「え、すごいじゃん!」。こんな変な会話しているのは受験生?それとも沿線の東工大の学生?素数とは1と自分自身だけでしか割り切れない孤独な数。素数がどういう順番で出現するのかは数学永遠の謎。だから、3並び1がすべて素数になるなんて、ありえない法則なのだ。私も素数オタクなのでこの話は知っていた。3が七つ並ぶところまでは素数だが次の、333333331は、残念ながら17で割り切れてしまう。つまり規則は崩れる。
 ・・・(中略)
 ちなみに2017は素数。割り切れない。でも虚数を使うときれいに因数分解できます。2017=(44―9i)(44+9i)
 ・・・

話の前半部分に、ふ~ん。やってみっか。こういう話は好きです。

★方針を立てなくっちゃ。
ある数が素数であるかどうかを判定するだけなら、比較的簡単。
偶数でないことをチェックしてから、3から始めてその数の平方根までの奇数で割ってみればいい。
割り切れる数があったら、その時点で「素数ではない。合成数だ」といって終わっていい。
そういうプログラムをまず書いてみましたが。何となく不満が残るんですね。
福岡さんの記事で、333333331は17で割り切れる、とあります。
333333331=17*1719607843
です。
ふむふむ。で、1719607843は素数だろうか、まだ割り切る数があるのかな。
気になりませんか?

★そうなってくると、素因数分解した方がいいようですね。
そうすれば1719607843がまだ分解できるかどうか報告が上がってくるでしょう。
じゃあ、素因数分解のプログラムをまず作ろう。
↓これが素因数分解のプログラム。
入力要求があるので、nを入力すると、素因数分解してくれます。
{言語は「(仮称)十進BASIC ver. 7.7.8」です。}
!***********************************
INPUT PROMPT "n = ":n   
LET rsvN = n
LET ans$ = ""

Do
   IF MOD(n, 2) = 0 THEN
      LET ans$ = ans$ & "2 "
      LET n = n / 2
   Else
      Exit Do
   End If
Loop
LET m = 3
DO WHILE(m <= SQR(n))
   IF MOD(n, m) = 0 THEN
      LET ans$ = ans$ & STR$(m) &" "
      LET n = n / m
   ELSE
      LET m = m + 2
   END IF
LOOP

PRINT STR$(rsvN);" "; 
IF (ans$ = "")OR(rsvN = 1)OR(rsvN = 2) THEN
   PRINT "素数です."
ELSE
   IF (n = 1)THEN
      PRINT ans$
   ELSE
      PRINT ans$ & STR$(n)
   END IF
END IF

END
!***********************************

実行例
n = 100
100 2 2 5 5

n = 2016
2016 2 2 2 2 2 3 3 7

n = 2017
2017 素数です.

n = 2018
2018 2 1009

本当は、2018 = 2 * 1009
とか出るようにすればいいのですが、できますけど、プログラムの流れが煩瑣になるのでやめました。
今回はここまで。次回は、このプログラムを使って、「333333331は素数か」どうか調べてみましょう。

« 白梅 | トップページ | 333333331は素数か:2 »

理科おじさん」カテゴリの記事

コメント

コメントを書く

(ウェブ上には掲載しません)

« 白梅 | トップページ | 333333331は素数か:2 »

2017年9月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
サイト内検索
ココログ最強検索 by 暴想
無料ブログはココログ