Introduction

The problem that the execution time is long when the input integer is a prime number in the previously created Prime factorization ver.1 of the integer input in Python. To solve.

Actual program

from sympy import primerange
 inn = n = int (input ("Please enter the number you want to check if it is a prime number. >>"))
num = int(n**(1/2)) + 1
primlist = list(primerange(2,num)) 
yaku = []

for i in primlist:
    if inn % i == 0: #1
 print (inn, "is a composite number.")
        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 ("Prime factorization", yaku, ".")
        break
    elif i == primlist[-1] :
 print (inn, "is a prime number.")

change point

In order to solve the problem that the judgment when it is a prime number is too slow, it is judged whether the integer input before performing the prime factorization in # 1 is a prime number. If it is a composite number, the processing from # 2 onward is performed. I added the if syntax of # 3 to display the result immediately when the factorization of n is completed before going to the end of the prime list.

Speed comparison

I measured the time using %% timeit of jupyter Notebook. We used 2281607 as a 7-digit prime number and 5241234 (2 x 3 x 873539) as a 7-digit composite number. Prime number 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)

Composite number 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)

Consideration

The execution speed when a prime number is input is 1.98 ** s ** → 1.17 ** ms **, which is a significant speed improvement. However, when the composite number was entered, the actual processing method itself did not change, so no improvement was observed as 4.63 s → 4.56 s.

Reflections

I am satisfied for the time being because I was able to improve the execution speed when the prime number was the target this time. However, unless the method of performing prime factorization is improved, the essential speed cannot be improved, so I would like to address this point. Thank you for reading to the end.