素数・素因数

ファクタリング」の概念は、整数で定義されています。したがって、ある数（整数）の因数とは、元の整数をヒントを残さずに第三の整数に分割する別の整数のことである。ある数の因数は、1とその数自身からなる。例えば、8の因子は、1、-1、2、-2、4、-4、8、-8である。

素数

素数とは、1より大きい自然数で、1およびその数自身によってのみ割り切れるものをいう。したがって、素数には、1つの因子とその数自体の2つの因子しかない。例えば、5が素数であるのは、1とその数自身でしか割り切れないからである。2つ以上の因子を持つ正の整数を合成数と呼ぶ。これは、2より大きい数字を持っているからです。素数を生成するための公式は存在しない。ある数が素数であることを証明するためには、その数が1とその数以外の因子を持たないことを、除数と潜在的因子の数学的手法を用いて証明する必要がある。

主な要因

各整数には少なくとも2つの因子がある。これらの因子のうち、いくつかは素数である可能性があります。これらは素因数と呼ばれる。つまり、ある数の素因数は、その数の因数であり、それはまた素数である。したがって、2は8の素因数である。しかし、8の他の因子は素因数ではないし、4は合成数なので8の素因数でもない。

整数を素因数の積として表現することを素因数分解といいます。まず、数字の中に2の因子があるかどうかを調べ、できるだけ多くの因子を取り除こうとする。そして、次の素数3を試し、3の因子をできるだけ多く取り除く。素数の積で表されるようになるまで、この作業を繰り返す。

例えば、840の素因数を求めてみましょう。

840 含有率2

840 = 2 x 420

420 含有率2

840 = 2 x 2 x 210

210 含有率2

840 = 2 x 2 x 2 x 105

105は2で割り切れるので、3は105の素因数である。

840 = 2 x 2 x 2 x 3 x 35

ただし、35は5で割り切れるので、5は35の素数である。

840 = 2 x 2 x 2 x 3 x 5 x 7

7はそれ自体が素数なので、840は以下のように素因数の積として書くことができる。

840 = 2 x 2 x 2 x 3 x 5 x 7

素因数を取り除くと、さらに着目する数字が常に少なくなっていくのです。