Prime factorization ver.2 of integers input in Python

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.

Recommended Posts

Prime factorization ver.2 of integers input in Python
Prime factorization of integers entered in Python ver.1
[Python 3] Prime factorization in 14 lines
Reversible scrambling of integers in Python
Key input in Python
Project Euler # 10 "sum of prime numbers" in Python
Key input in Python
Prime numbers in Python
Prime number 2 in Python
Python Input Note in AtCoder
Equivalence of objects in Python
Implementation of quicksort in Python
[For beginners] Summary of standard input in Python (with explanation)
Pixel manipulation of images in Python
Division of timedelta in Python 2.7 series
Infinite prime number generator in Python3
Handling of JSON files in Python
Implementation of life game in Python
Waveform display of audio in Python
Let's see using input in python
Law of large numbers in python
Implementation of original sorting in Python
Conversion of string <-> date (date, datetime) in Python
Project Euler # 3 "Maximum Prime Factors" in Python
Data input / output in Python (CSV, JSON)
Check the behavior of destructor in Python
(Bad) practice of using this in Python
General Theory of Relativity in Python: Introduction
Output tree structure of files in Python
Display a list of alphabets in Python 3
Comparison of Japanese conversion module in Python3
Project Euler # 7 "1000 1st prime number" in Python
The result of installing python in Anaconda
Gang of Four (GoF) Patterns in Python
The basics of running NoxPlayer in Python
Bulk replacement of strings in Python arrays
Project Euler # 16 "Sum of Powers" in Python
Summary of built-in methods in Python list
I searched for prime numbers in python
Non-logical operator usage of or in python
In search of the fastest FizzBuzz in Python
Practical example of Hexagonal Architecture in Python
Project Euler # 17 "Number of Characters" in Python
Double pendulum equation of motion in python
Get rid of DICOM images in Python
[Python] Chapter 02-03 Basics of Python programs (input / output)
Status of each Python processing system in 2020
Project Euler # 1 "Multiples of 3 and 5" in Python
Meaning of using DI framework in Python
Japanese translation of self-study "A Beginner's Guide to Getting User Input in Python"
Type in Python to implement algebraic extension (1) ~ Monoids, groups, rings, ring of integers ~
Output the number of CPU cores in Python
Draw a graph of a quadratic function in Python
[Python] Sort the list of pathlib.Path in natural sort
Receive websocket of kabu station ® API in Python
Unattended operation of Google Spreadsheets (etc.) in Python
Get the caller of a function in Python
Match the distribution of each group in Python
View the result of geometry processing in Python
Prime number enumeration and primality test in Python
Make a copy of the list in Python