2以上の整数を、素数と合成数、に分けることができる。

素数とは1と自分自身でしか割り切ることのできない数。例えば、2, 3, 5, 7, 11... 無限個に存在する。

合成数とは素数以外の数、つまり、1と自分自身以外にも、ある整数(約数という)で割り切ることのできる数。例えば、4, 6, 8, 9, 10, 12... 無限個に存在する。

ここでいう数Nの約数とは、その数Nをを割り切れる整数のこと。素数は約数の数が2つ、合成数は約数の数が3以上。

合成数は素数の積で表すことができる。これを素因数分解という。たとえば、720 = 24x32x51

素因数分解できれば、約数の数を計算することは簡単だ。例えば、上の720では、それぞれの 指数の数+1の積 がその答えになる。(4+1) x (2+1) x (1+1) = 30。つまり、異なる30個の約数をもっている。小さい順で書くと、

になる。

さて、ここからが難しい問題。

 素因数 2,3 5をもつ合成数を小さい順で並べておき、1500番目の数を計算せよ。

つまり、数列 2mx3kx5t の n番目を算出する問題。この合成数列を小さい順で12個書くと以下になる。

因みに、この数列の30番目の数は80であり、720ではない。

計算の方法についてだが、思いつけば案外簡単。出発点は、つぎの13番目の合成数は、前にある12個の数から、素因数 2, 3, 5 のどれかで掛けてできた値という事実。そこで、力まかせで、12 x 3 計36回の掛け算をし、36個の積から、(12番目の)16より大きな最小数を探し出し、それをつぎの13番目にすればいいわけだ。

ということで、テーブルを用意して、計算できたN番目までの合成数を小さい順でテーブルに格納する。つぎのN+1番目の合成数は、上の方法で KN回(Kは素因数の数、いまの例では3)掛け算をし、N番目よりも大きな、最小積がそれとなる。

計算量は明らかにO(KN)だが、数列の1番目から1つずつ計算しないといけないので、全体的に、N番目の数を算出するまでの計算量は、O(KN2) となる。

以下はC言語プログラム。あくまでも参考程度。

では、練習問題をどうぞ。
A number whose only prime factors are 2,3,5 or 7 is called a humble number. The sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, ... shows the first 20 humble numbers.
Write a program to find and print the nth element in this sequence.

Comments are closed.

Post Navigation