なぜ小さい順にある数を割っていくプログラムが素因数分解になるのか？【考察】

calculatedvalue = []

    for i in range(2, num):

        while num % i == 0:

            num = num / i

            calculatedvalue.append(i)

　このプログラムは2以上の整数を素因数分解をして素因数のlistを作ります。

　しかし除数が素数であるか確認しないため、「合成数を素数として扱い、素因数分解する」と思うかもしれません。それがありえない理由を考察を交えて説明します。

全ての整数は素数の積で表せる。

　適当な整数を思い浮かべてください。今思い浮かべたその整数は、ある整数の積で必ず表せます。ある整数というのは、1とその整数自身です。つまり全ての整数は1nとなります。1は素数なので、結果的に全ての整数は1nで表せます。

　次に全ての整数が素数の積で表せる事を説明します。まず素数は1nで表せます。これは絶対で、これ以外の組み合わせもありません。また素数の素数倍も素数の積です。全ての整数は素数の積なので、全ての整数は素数の積です。

全ての整数は素数の積なので

　ある合成数(=n)は素数の積です。つまりそれらを構成する素数(=N)はnより小さい、あるいは等しいという事になります。一番上のプログラムは小さい順に試行するので、nよりもNが先に出てきます。(負の値はこれに限りません。)nで割り切れる値はnの約数であるNでも割り切れるので、nよりも先にNで割られるわけです。ちなみに負の値の場合は、-nを-1nとしてもいいかもしれません。

(詳しくもないのに偉そうに書いてみました。)