Pythonで入力された整数を素因数分解 ver.2

はじめに

以前作成したPythonで入力された整数を素因数分解 ver.1での、入力された整数が素数だった場合の実行時間が長い問題を解決します。

実際のプログラム

from sympy import primerange
inn = n = int(input("素数か確かめたい数を入力してください。>> "))
num = int(n**(1/2)) + 1
primlist = list(primerange(2,num)) 
yaku = []

for i in primlist:
    if inn % i == 0: #1
        print(inn,"は合成数です。")
        for i in list(primerange(i, (n +1)/i)):  #2
            if n == 1:　#3
                break
            while n % i == 0:
                n /= i
                yaku.append(i)

        print("素因数分解すると",yaku, "です。")
        break
    elif i == primlist[-1] :
        print(inn, "は素数です。")

変更点

素数だった際の判定が遅すぎることを解決するために、#1で素因数分解を行う前に入力された整数が素数か判定するようにしました。
合成数だった場合は、#2から先の処理を行うようにしてあります。#3の if 構文は、素数リストの最後まで行く前に n の素因数分解が完了した際に即座に結果を表示する為に付け加えました。

速さの比較

jupyter Notebook の %%timeit を用いて時間を測定しました。
7桁の素数として2281607、7桁の合成数として5241234(2×3×873539)を用いました。
素数
ver.1：1.98 s ± 30.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
ver.2：1.17 ms ± 25.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

合成数
ver.1：4.63 s ± 40.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
ver.2：4.56 s ± 75.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

考察

素数が入力された際の実行速度は1.98 s → 1.17 ms と大幅な速度改善ができました。しかし、合成数が入力された場合では実際の処理方法自体が変わっていないので4.63 s →4.56 s と改善が認められませんでした。

反省点

今回の目標であった素数であった場合の実行速度の改善ができたので一先ず満足しています。ただ、素因数分解を行う方法を改善しない限り本質的な速度改善ができないので、この点を詰めていきたいと思います。
最後まで読んで下さいまして有難うございました。